C++ - 최빈값 구하기

Об этом предложении

1. 슈도코드 배열 array 를 순회하며 map에 숫자(key)별 등장 횟수(value) 를 저장한다. map을 순회하며 등장 횟수가 가장 큰 숫자 를 찾는다. 최빈값이 여러 개면 -1 을, 하나면 그 숫자를 반환한다. 2. 실제코드 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> #include <map> int solution(int array[], size_t array_len) { int answer = 0; map<int, int> countMap; for(int n : array) { countMap[n]++; } int maxCount = -1; int value = -1; bool isMultiValue = false; for(auto& iter : countMap) { if(iter.second > maxCount) { maxCount = iter.second; value = iter.first; isMultiValue = false; } else if(iter.second == maxCount) { isMultiValue = true; } } return isMultiValue ? -1 : value; } 전처리 지시문 #include <map> map 을 사용하기 위한 전처리 지시문이다. 숫자별 등장 횟수 세기 for (int n : array) { countMap[n]++; } array 의 원소를 하나씩 꺼내 n 에 담고, countMap[n] 의 값을 1 증가시킨다. countMap[n] 은 n을 key로 하는 value 에 접근한다. 처음 등장하는 key라면 value가 0으로 자동 생성 된 뒤 ++ 로 1이 된다. 이미 있는 key라면 기존 value에 1이 더해진다. 예시: {1, 2, 3, 3, 3, 4, 5} 꺼낸 값 (n) 동작 countMap 상태 1 key 1 생성 → 1 {1:1} 2 key 2 생성 → 1 {1:1, 2:1} 3 key 3 생성 → 1 {1:1, 2:1, 3:1} 3 key 3 증가 → 2 {1:1, 2:1, 3:2} 3 key 3 증가 → 3 {1:1, 2:1, 3:3} 4 key 4 생성 → 1 {1:1, 2:1, 3:3, 4:1} 5 key 5 생성 → 1 {1:1, 2:1, 3:3, 4:1, 5:1} 최종적으로 countMap 에는 숫자(key)와 그 숫자의 등장 횟수(value) 가 저장된다. 같은 key는 하나만 존재하고, 값이 다시 나올 때마다 value만 증가 한다는 점이 핵심이다. 최빈값 뽑기 int maxCount = -1; // 지금까지 본 가장 큰 등장 횟수 int value = -1; // 그 횟수를 가진 숫자 (최빈값 후보) bool isMultiValue = false; // 최빈값이 여러 개인지 여부 for (auto& iter : countMap) { if (iter.second > maxCount) { maxCount = iter.second; value = iter.first; isMultiValue = false; } else if (iter.second == maxCount) { isMultiValue = true; } } return isMultiValue ? -1 : value; countMap 을 처음부터 끝까지 돌면서 등장 횟수가 가장 큰 숫자 를 찾는다. iter.first : key (숫자) iter.second : value (등장 횟수) auto& : map의 원소를 복사하지 않고 참조로 가져온다. 조건별 동작 더 큰 횟수를 찾은 경우 ( iter.second > maxCount ) 새로운 최빈값이므로 maxCount 와 value 를 갱신한다. 이전에 동률이 있었더라도 더 큰 값이 나왔으니 isMultiValue 를 false 로 되돌린다. 같은 횟수를 찾은 경우 ( iter.second == maxCount ) 최빈값이 여러 개라는 뜻이므로 isMultiValue 를 true 로 바꾼다. maxCount 를 -1 로 시작하는 이유는 첫 번째 원소가 무조건 첫 조건에 걸려 최빈값 후보로 들어가게 하기 위해서다. 예시: {1, 2, 3, 3, 3, 4, 5} → countMap {1:1, 2:1, 3:3, 4:1, 5:1} iter 비교 maxCount value isMultiValue (1, 1) 1 > -1 → 갱신 1 1 false (2, 1) 1 == 1 → 동률 1 1 true (3, 3) 3 > 1 → 갱신 3 3 false (4, 1) 1 < 3 → 무시 3 3 false (5, 1) 1 < 3 → 무시 3 3 false 결과는 isMultiValue 가 false 이므로 3 을 반환한다. 최빈값이 여러 개인 경우: {1, 1, 2, 2} → countMap {1:2, 2:2} iter 비교 maxCount value isMultiValue (1, 2) 2 > -1 → 갱신 2 1 false (2, 2) 2 == 2 → 동률 2 1 true isMultiValue 가 true 이므로 -1 을 반환한다. 반환 return isMultiValue ? -1 : value; 삼항 연산자로, isMultiValue 가 true 면 -1 , 아니면 value 를 반환한다. 3. 중요 포인트 map으로 등장 횟수 세기 숫자별 개수를 셀 때는 map<int, int> 를 사용하면 편하다. (key: 숫자, value: 등장 횟수) countMap[n]++ 한 줄로 개수를 셀 수 있다. 처음 나온 key는 value가 0으로 자동 생성되기 때문에 따로 초기화할 필요가 없다. 반복문 한 번으로 최빈값 찾기 map을 순회하면서 지금까지의 최대 횟수( maxCount ) 와 비교해 최빈값을 갱신한다. 최빈값이 여러 개인지 확인하기 위해 isMultiValue 같은 bool 변수(플래그) 를 함께 사용한다. 같은 횟수가 나오면 true 더 큰 횟수가 나오면 다시 false 로 초기화 (이전 동률은 더 이상 최빈값이 아니므로) maxCount 를 -1 로 시작해야 첫 번째 원소가 반드시 최빈값 후보로 들어간다.