프로그래머스 - 폰켓몬

• 문제 링크

초기 접근 및 로직 구상 방식

N/2마리를 뽑는 모든 조합을 나열하고, 그중 종류가 겹치는 조합을 제외한 뒤 종류 수가 최대인 걸 고를려고 했는데, N=10,000이라 나열하기에는 너무나 많음. 아닌거 같다는 생각이 드는데, 막상 떠오르지 않아서 질문을 함.

힌트 1 nums = [1,2,3,4]. N=4니까 2마리 뽑아서 손으로 나열해보기. 종류는 4개 있어. 종류 수는 몇 개고, 왜 4가 될 수 없는지.

주어진 예시로, nums = [1,2,3,4]. N=4 라면, 12,13,14,23,24,34. 이렇게 나오는데, 종류는 4마리, 뽑아야 할 수는 2마리.중복 없이 몇 마리가 가능하냐를 물어 보는것이니, 12 또는 13 또는 14 또는… 이런식으로니깐 총 2종류. 즉, 종류의 수인데, 뽑는 수가 정해져있다면, 종류의 수는 거기에 맞춰서 한정됨.

뽑을 수는 이미 nums.length / 2 로 주어졌고, 종류만 구하면 되니깐, HashSet으로 1이라는 종류가 있고, 2라는 종류가 있는지 알려주기만 하면된다. 개수는 필요 없음.

제출

1차 제출

• 성공.

배운 점

• min으로 하는 이유는, 종류의 수가 가질 수 있는 다양한 마리의 수인데, 그것을 뽑는 수로 제한을 두니깐.
• 개수가 필요한가, 존재 여부만 필요한지에 Set(존재 여부)과 Map(개수)이 갈림.
• 이 문제에서는 종류가 있다는 건, 최소 1마리가 있다는 것이니, 종류가 있냐, 없냐만 알면 됨으로 Set으로 충분.
• set.add(x)은 map.put(x, 더미값)이랑 같음.
• 해시에서 add는 값으로 위치를 한번 계산해서 그 위치만 보기때문에, 평균 O(1). 이걸 N번 만큼 한바퀴 돌리면, O(N)이 나옴. 따라서 최종 코드는 O(N)이 나옴.

최종 풀이 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        int answer = Math.min(set.size(), nums.length / 2);
        return answer;
    }
}