문제 설명
짝수 길이의 배열이 하나 주어져 있다고 가정해 봅시다. 배열 안의 서로 다른 숫자는 서로 다른 종류의 사탕을 의미하며, 각 숫자 하나는 해당 종류의 사탕 한 개를 나타냅니다. 우리는 이 사탕들을 오빠와 여동생에게 수량상 동일하게 나누어 주어야 하고, 이때 여동생이 받을 수 있는 사탕 종류의 최대 개수를 구하는 것이 목표입니다.
예를 들어 입력이 [1,1,2,3]이라면 출력은 2가 됩니다. 여동생에게 [2,3]을, 오빠에게 [1,1]을 나누어 주면, 여동생은 두 가지 종류의 사탕을 갖게 되지만 오빠는 한 가지 종류만 갖게 됩니다. 즉, 여동생이 가질 수 있는 서로 다른 사탕 종류의 최대 개수는 2입니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 여동생은 전체 사탕의 정확히 절반(n/2개)만 받을 수 있으므로, 사탕의 종류 수가 n/2보다 많더라도 실제로 가질 수 있는 최대 종류 수는 n/2를 넘을 수 없습니다. 반대로 종류 수가 n/2보다 적다면, 모든 종류를 하나씩 여동생에게 줄 수 있으므로 종류 수가 곧 정답이 됩니다. 이를 코드로 구현하면 다음 단계를 따릅니다.
- 중복을 자동으로 제거해 주는 정수 저장용 집합(unordered_set) s를 하나 정의합니다.
- i를 0부터 candies 배열의 크기 미만까지 1씩 증가시키며 반복하면서, 각 원소 candies[i]를 s에 삽입합니다. 이 과정이 끝나면 s에는 서로 다른 사탕의 종류 수만 남습니다.
- s의 크기(사탕 종류 수)와 candies.size() / 2(여동생이 받을 사탕 개수) 중 더 작은 값을 반환합니다.
예시 코드
아래의 C++ 구현 예제를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int distributeCandies(vector<int>& candies){
unordered_set<int> s;
for (int i = 0; i < candies.size(); i++)
s.insert(candies[i]);
return min(s.size(), candies.size() / 2);
}
};
main(){
Solution ob;
vector<int> v = {1,1,2,3};
cout << (ob.distributeCandies(v));
}입력
{1,1,2,3}출력
2
복잡도 분석
- 시간 복잡도: O(n) — 배열의 모든 원소를 한 번씩 순회하며 집합에 삽입합니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 사탕의 종류가 서로 달라 집합에 n개의 원소가 저장될 수 있습니다.