문제 소개
숲속에 살고 있는 토끼들은 각자 서로 다른 색을 가지고 있다고 가정해 봅시다. 이제 토끼들 중 일부(전부일 수도 있습니다)가 자신과 같은 색을 가진 다른 토끼가 몇 마리인지 대답하고, 그 대답들이 하나의 배열에 담겨 있습니다. 우리의 목표는 숲속에 있을 수 있는 토끼의 최소 마리 수를 구하는 것입니다.
예를 들어 입력이 [1, 1, 2]라면 출력은 5가 됩니다. 그 이유는 다음과 같습니다. "1"이라고 대답한 두 마리의 토끼는 서로 같은 색, 예를 들어 흰색일 수 있습니다. 그런데 "2"라고 대답한 토끼는 흰색일 수 없습니다. 만약 흰색이라면 앞선 대답들과 모순되기 때문입니다. "2"라고 대답한 토끼가 검은색이라고 가정하면, 배열에 대답하지 않은 검은색 토끼가 2마리 더 있어야 합니다. 따라서 숲속 토끼의 최소 마리 수는 대답한 3마리 + 대답하지 않은 2마리 = 5마리가 됩니다.
해결 접근 방법
이 문제는 그리디(Greedy) 기법과 해시 맵을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 어떤 토끼가
x라고 대답했다면, 같은 색의 토끼는 총x + 1마리 존재해야 합니다(자기 자신 포함). - 같은 대답
x를 한 토끼들은 가능한 한 같은 색 그룹으로 묶어야 최솟값을 얻을 수 있습니다. - 한 그룹에
x + 1마리가 모두 차면, 그다음x라고 대답하는 토끼는 새로운 색 그룹을 만들어야 합니다. 0이라고 대답한 토끼는 같은 색의 다른 토끼가 없다는 뜻이므로, 각자 독립적으로 1마리씩 카운트합니다.
알고리즘 단계
- 맵
m을 생성하고, 배열ans의 크기를n에 저장합니다. - 결과값
ret을 0으로 초기화합니다. i를 0부터n - 1까지 반복합니다.x := ans[i]x = 0이면ret을 1 증가시키고 다음 반복으로 넘어갑니다.- 맵
m에x가 존재하지 않으면,ret을(x + 1)만큼 증가시키고m[x] := 0으로 설정합니다. 이는 새로운 색 그룹이 시작되었음을 의미합니다. - 맵에
x가 이미 존재하면:m[x]를 1 증가시킵니다.m[x] = x가 되면 해당 그룹이 가득 찬 것이므로 맵에서x를 삭제합니다.
- 최종적으로
ret을 반환합니다.
C++ 구현 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRabbits(vector<int>& ans) {
map <int, int> m;
int n = ans.size();
int ret = 0;
for(int i = 0; i < n; i++){
int x = ans[i];
if(x == 0){
ret++;
continue;
}
if(!m.count(x)){
ret += (x + 1);
m[x] = 0;
}else{
m[x]++;
if(m[x] == x){
m.erase(x);
}
}
}
return ret;
}
};
main(){
vector<int> v = {1,1,2};
Solution ob;
cout << (ob.numRabbits(v));
}입력
[1,1,2]
출력
5
복잡도 분석
이 알고리즘의 시간 복잡도는 배열을 한 번만 순회하므로 O(n)이며, 공간 복잡도는 서로 다른 대답의 종류 수에 비례하여 최악의 경우 O(n)입니다. 맵을 활용해 각 색 그룹의 현재 채워진 상태를 추적하기 때문에, 대답한 토끼들을 최대한 효율적으로 그룹화하여 숲속 토끼의 최소 마리 수를 정확하게 계산할 수 있습니다.