폰켄몬

코딩 테스트 문제

프로그래머스

 

제안사항은 아래와 같이 입력되어있습니다.

nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

위 문제는 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾는 문제입니다.

 

문제 접근)
1. 다양한 폰켓몬 종류를 선택할 수 있는 최댓값을 구하는 것이므로, 같은 종류의 폰켓몬은 의미가 없으므로 해시맵을 사용해서 해결하면 될 것 같습니다.

2. 폰켓몬 종류 번호가 몇개이든 뽑는 가장 많은 종류수가 중요하므로  종류번호는 시간복잡도와 연관이 없고, nums의 갯수가 길어짐에 따라 시간복잡도가 달라지는데 10^4 이므로 시간 복잡도 O(n^2) 미만으로 풀어야 합니다. 그러므로 시간 복잡도 O(n)미만 시간복잡도를 이용하여 풀면 됩니다. 해시맵은 시간복잡도가 O(1)이므로 해시맵으로 해결하도록 하겠습니다.

 

 

 

Solution

function solution(nums) {
    const set = new Set([...nums]);
    const pickLimit = nums.length / 2;
    return set.size > pickLimit ? pickLimit : set.size
}

 

입출력 예제를 보면, 다양한 종류를 원하므로 해시맵으로 nums(폰켓몬 종류들)을 중복되는 종류를 제거하여 set을 구합니다.

그리고 그 중에서 pickLimit(뽑을 수 있는 갯수)는 nums(폰켓몬 종류들)/2 이므로 값을 구합니다.

그러면 입출력 예제는 아래와 같은 결과를 같습니다.
[3,1,2,3]
{ set: Set(3) { 3, 1, 2 }, pickLimit: 2 }
-> 종류가 3, 1, 2가 있고, pickLimit이 2개 이므로 3,1과 1,2과 2,3 어떻게 하든 폰켓몬 종류의 수는 2라는 결과 값이 나옵니다.

[3, 3, 3, 2, 2, 4]
{ set: Set(3) { 3, 2, 4 }, pickLimit: 3 }
-> 종류가 3, 2, 4가 있고, pickLimit이 3개 이므로  최대 고를 수 있는 폰켓몬 종류의 수는 3라는 결과값이 나옵니다.

[3, 3, 3, 2, 2, 2]
{ set: Set(2) { 3, 2 }, pickLimit: 3 }
-> 종류가 3, 2 두개 밖에 없으므로 pickLimit이 3개라도 최대 고를 수 있는 폰켓몬 종류의 수는 2라는 결과값이 나옵니다.

 

즉 이 입출력 예제를 보면 폰켓몬 종류가 pickLimit보다 크면 고를 수 있는 pickLimit 만큼의 종류수를 고를 수 있고,  그 반대의 경우는 아무리 고를 수 있는 갯수가 많아도 폰켓몬 종류가 적으면 폰켓몬 종류 수 만큼의 결과를 도출합니다.

그래서 set.size > pickLimit ? pickLimit : set.size의 결과를 반환하면 해결 할 수 있습니다.