[Problem Solving] 폰켓몬

Sean·2023년 1월 12일

Problem Solving

목록 보기

23/130

문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
두 번째(1번), 세 번째(2번) 폰켓몬을 선택
두 번째(1번), 네 번째(3번) 폰켓몬을 선택
세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

조건

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

❌틀린 풀이

아이디어

내가 뽑을 포켓몬의 수 N/2와 nums 배열에 있는 폰켓몬의 총 종류의 수의 대소 관계만 비교하면 된다.
- N/2 > 종류의 수 : answer = 종류의 수
- N/2 < 종류의 수 : answer = N/2
위의 아이디어가 틀린 것은 아니고, 폰켓몬의 종류의 수를 세는 방법이 잘못됐다. 예제만 보고 무조건 nums 배열에 종류의 번호가 연속적으로 이어져있을 거라는 생각으로 코드를 짰기 때문이다. 그래서 종류의 수를 nums 배열에 있는 최댓값 - 최솟값 + 1로 정했다.

코드

function solution(nums) {
    var answer = 0;
    var max = Math.max(...nums),
        min = Math.min(...nums);
    var N = nums.length;
    
    // 뽑는 개수: N/2 개
    // 종류의 가짓수: max-min+1 가지
    
    (max-min+1 >= N/2) ? answer=(N/2) : answer = (max-min+1); 
    
    return answer;
}

⭕통과한 풀이

nums 배열에서 폰켓몬의 종류의 수를 뽑아내는 방법을 다르게 하였다.

아이디어

JavaScript의 내장 객체 Map을 사용한다.
nums 배열을 순회하면서 어떤 수가 나오면 Map에서 해당 수를 key로 가지고 있을 경우 value로 카운트를 하나 늘려주고, Map에서 해당 수를 key로 가지고 있지 않다면 해당 수를 key로 만들어주고 카운트를 하나 늘려준다.
최종적으로 완성된 Map의 모든 요소의 개수가 폰켓몬의 종류의 개수이다.

코드

function solution(nums) {
    var answer = 0;
    var N = nums.length;
    var map = new Map();
    
    nums.forEach(n => {
        map.set(n, (map.get(n) || 0)+1);
    });
    
    var typecnt = map.size;
    
    // 뽑는 개수: N/2 개
    // 종류의 가짓수: map에 들어있는 요소들의 개수
    
    console.log('typecnt: ', typecnt);
    (typecnt >= N/2) ? answer=(N/2) : answer = typecnt; 
    
    return answer;
}

💡더 좋은 풀이

나는 Map을 사용했지만, 폰켓몬의 종류의 수를 세려면 같은 종류의 폰켓몬이 등장해도 카운트는 하지 않는다는 개념을 명확히 이해한다면, 이는 "집합"을 이용하면 되겠다는 생각으로 이어질 수 있고, JavaScript의 내장 객체 Set을 활용하면 되겠다는 결론에 다다를 수 있다.

Tip) Array에서 Set으로의 전환하기 위해서는 정규 Set 생성자를 사용해야 한다.
var myArray = ['value1', 'value2', 'value3'];

// Array를 Set으로 변환하기 위해서는 정규 Set 생성자 사용
var mySet = new Set(myArray);

코드

function solution(nums) {
  const pickNum = nums.length / 2;
  const typecnt = new Set(nums).size;
  
  return pickNum > typecnt ? typecnt : pickNum;
}

파이썬 코드

def solution(nums):
    typeset = set(nums)
    answer = 0
    target = len(nums)/2
    current = len(typeset)
    while True:
        if current >= target:
            answer = target
            break
        else:
            answer = current
            break
    
    return answer