- 전체
- 후기 6759
- 후기-카드 1815
- 후기-발권-예약 1241
- 후기-백신 79
- 후기-격리면제 28
- 질문 57148
- 질문-기타 20670
- 질문-카드 11679
- 질문-항공 10177
- 질문-호텔 5190
- 질문-여행 4032
- 질문-DIY 178
- 질문-자가격리 19
- 질문-은퇴 412
- 정보 24196
- 정보-자가격리 133
- 정보-카드 5214
- 정보-기타 8004
- 정보-항공 3824
- 정보-호텔 3231
- 정보-여행 1060
- 정보-DIY 205
- 정보-맛집 217
- 정보-부동산 39
- 정보-은퇴 259
- 여행기 3419
- 여행기-하와이 388
- 잡담 15468
- 필독 63
- 자료 64
- 자랑 722
- 금요스페셜 106
- 강퇴로 가는 길 11
- 자기소개 661
- 구라 2
- 요리-레시피 70
- 오프모임 200
- 나눔 2699
- 홍보 15
- 운영자공지 32
마일모아에서 이런걸 여쭤볼거라고는 생각 못했는데 여기 말고는 물어볼 데가 없어서...
Leetcode 477번 Total Hamming Distance 라는 문제가 있습니다.
풀이를 찾아보니...
int totalHammingDistance(vector<int>& nums) {
int res = 0, n = nums.size();
for (int i = 0; i < 32; ++i) {
int count = 0;
int mask = 1 << i;
for (int num : nums) {
if (num & mask) ++count;
}
res += count * (n - count);
}
return res;
}
이렇게 나와있는데요, 노란줄이 도대체 이해가 안갑니다. set bit의 갯수와 unset bit의 갯수를 곱하는게 무슨 의미가 있는지?
아시는 분 설명 좀 부탁드립니다.
- 전체
- 후기 6759
- 후기-카드 1815
- 후기-발권-예약 1241
- 후기-백신 79
- 후기-격리면제 28
- 질문 57148
- 질문-기타 20670
- 질문-카드 11679
- 질문-항공 10177
- 질문-호텔 5190
- 질문-여행 4032
- 질문-DIY 178
- 질문-자가격리 19
- 질문-은퇴 412
- 정보 24196
- 정보-자가격리 133
- 정보-카드 5214
- 정보-기타 8004
- 정보-항공 3824
- 정보-호텔 3231
- 정보-여행 1060
- 정보-DIY 205
- 정보-맛집 217
- 정보-부동산 39
- 정보-은퇴 259
- 여행기 3419
- 여행기-하와이 388
- 잡담 15468
- 필독 63
- 자료 64
- 자랑 722
- 금요스페셜 106
- 강퇴로 가는 길 11
- 자기소개 661
- 구라 2
- 요리-레시피 70
- 오프모임 200
- 나눔 2699
- 홍보 15
- 운영자공지 32
5 댓글
많이사
2019-06-21 00:47:34
원래 문제가 뭔지 모르겠지만 그냥 추측컨대, 모든 pair를 찾아서 각 pair의 distance를 sum 하는게 아니라 각 bit 별로 "다른" 페어들의 갯수를 구해서 최적화 한 것 같은데요. 예를 들어 0이 2개고 1이 4개면 디스턴스의 총 합을 6*5/2 페어를 돌아가며 계산해서 세는게 아니라 0 갯수 * 1 갯수 = 8 이런식으로 계산한 것 같습니다.
커피
2019-06-21 00:50:24
문제에서 요구하는 것은 n개의 수를 입력 받아서 nums[0], nums[1], ..., nums[n-1]의 binary representation으로 나타냈을 때 pairwise hamming distance를 구해서 총합을 구하는 것인데, 이 요구대로 정직하게 (i = 0 .. n-2 & j = i+1 .. n-1) 2중 for-loop을 이용하여 hamming_dist(nums[i], nums[j]) 를 더하는 방법이 있을테구요
본문에 적어주신 방법은 그보다 효율적으로 답을 구하는 방법입니다.
첫 번째 for loop 보시면 i를 [0, 31]까지 올리면서 입력으로 받은 n개의 정수 (nums)의 i번째 bit이 set 된것과 unset된 것의 개수를 셉니다.
정확히는 count variable에 i번째 bit이 set된 개수 (이 값은 0 이상 n이하 이겠죠)가 될거고,
각 i에 대해서 count * (n - count)가 나타내는 quantity는 우리가 최종적으로 구하고 싶은 전체 hamming distance 총합을
0번째, 1번째, .., 31번째 비트로 쪼개서 구해서 더했다고 생각하면 됩니다.
예를 들면 문제에서 나온대로 4, 14, 2의 경우 2진수로 나타내면 (편의상 4개씩 끊어서 적었습니다)
0000 0000 0000 0000 0000 0000 0000 0100 = 4
0000 0000 0000 0000 0000 0000 0000 1110 = 14
0000 0000 0000 0000 0000 0000 0000 0010 = 2
US빌리언달라맨
2019-06-21 01:00:28
이게 수학 문젠가요? 언제 배우는건가요? 궁금해서 여쭤 봅니다
armian98
2019-06-21 00:53:06
문제가 숫자들 간의 hamming distance의 총 합을 구하는 것인가봅니다. hamming distance면 bit이 다를 때 1씩 올라가는 건데, 각 bit에 대해서 그 bit이 0인 숫자들의 갯수 (n - count)랑 1인 숫자들의 갯수 (count)들 간에만 거리가 1 생기니까 그 bit에서 생기는 거리의 총 합이 count * (n - count)가 되네요. (count) 숫자들이랑 (n - count) 숫자들로 pair를 만들 수 있는 방법의 수라고 생각하시면 될 것 같습니다.
얼마에
2019-06-21 01:07:35
#이과망했으면