[코딩테스트] Programmers - 폰켓몬 (성공)

 

https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=java

프로그래머스

 

풀이

문제가 오래되어서 그런지 c#으로 제출하지 못한다. 

일단 주력 언어가 c#이니 c#으로 풀어봤다. 

 

문제 요약부터 해보자. 

 

문제 

• N마리 폰켓몬 중 N/2마리를 가져가도 된다.
• 폰켓몬은 종류에 따라 번호를 붙여 구분한다. (같은 종류 폰켓몬은 같은 번호다)
• 다양한 종류의 폰켓몬을 가지고 싶다. 최대한 많은 종류의 폰켓몬으로 N/2마리 선택하자. 

 

입력

• N마리 폰켓몬 종류 번호 배열 nums 

 

출력

• 가장 많은 종류의 폰켓몬을 선택하는 방법으로 폰켓몬 종류 번호 개수를 반환 

제한사항

• nums = 1차원 배열
• 1 <= nums 길이 <= 10,000, nums길이는 짝수
• 1 <= 폰켓몬 종류 번호 <= 200,000
• 가장 많은 종류의 폰켓몬 선택 방법이 여러 가지이면, 선택할 수 있는 폰켓몬 종류 개수 최댓값을 리턴 

 

nums배열에서 n/2만큼 폰켓몬을 가져가야 한다.

종류는 최대한 많이 되도록 가져가야 한다. 

 

일단 문제 유형은 해시인데. 어떻게 풀지 잘 모르겠으니 일단 예시로 나온 것들을 묶어봤다. 

 

예제 1

nums = [3, 1, 2, 3]

3 -> 2개

1 -> 1개

2 -> 1개 

 

여기서 2개(n/2)를 뽑되 종류 수가 가장 많게 뽑아야 한다. 눈대중으로 보면 최대 종류 수는 2개다. 

 

예제 2

nums = [3, 3, 3, 2, 2, 4]

3 -> 3개

2 -> 2개

4 -> 1개 

 

여기서 3개(n/2)를 뽑되 종류 수가 가장 많게 뽑아야 한다. 최대 종류 수는 3개다. 

 

이렇게 보면 최대 종류 수는 n/2인 것 같은데, 예제 3을 보면 아니라는 것을 알 수 있다. 

 

예제 3

nums = [3, 3, 3, 2, 2, 2]

3 -> 3개

2 -> 3개

 

여기서 3개(n/2)를 뽑되 종류 수가 가장 많이 뽑아야 한다. 최대 종류 수는 2개다. 

 

어떻게 풀까 고민하던 중 일단 해시 문제이니 Dictionary를 사용하면 되겠고

폰켓몬 종류를 키값으로 하고 종류의 개수를 저장하는 Dictionary를 만들고 nums 배열로 종류와 개수를 저장했다고 치면

Dictionary에서 키값을 하나씩 가져와서 n/2개를 뽑으면 되지 않을까? 

다 뽑히면 n/2를 반환하고, 다 뽑히지 않으면 뽑은 만큼이 최대 종류 수이니까. 

 

시간복잡도를 생각해 보자. 

우선 Dictionary에 폰켓몬 종류와 개수를 저장하는데 nums배열 길이만큼 걸리겠고 ( O(10,000) )

Dictionary의 킷값을 가져와서 n/2를 차감하는 연산은 최대 200,000만큼 연산이 걸리겠다. ( O(200,000) ) 

10,000 + 200,000 = 210,000번 연산이 일어난다. 1초 내로 풀 수 있다. 

이 방식으로 풀어보자. 

 

 

코드 1 - 정답 

public int solution(int[] nums)
{
    // 딕셔너리에 넣기 
    Dictionary<int, int> dict = new Dictionary<int, int>();
    for(int i = 0; i < nums.Length; i++)
    {
        if (!dict.ContainsKey(nums[i]))
            dict.Add(nums[i], 1);
        else
            dict[nums[i]]++;
    }    

    int n = nums.Length / 2;
    int count = n;
    // 키 나열하고 
    foreach(int key in dict.Keys)
    {
        dict[key] -= 1;
        count--; 
    }

    if(count == 0)
        return n; 
    else
        return n - count;
}

 

 

코드 2 (자바 코드)

import java.util.HashMap;

public class Solution {
    public int solution(int[] nums) 
    {
        HashMap<Integer, Integer> dict = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!dict.containsKey(nums[i])) {
                dict.put(nums[i], 1);
            } else {
                dict.put(nums[i], dict.get(nums[i]) + 1);
            }
        }    

        int n = nums.length / 2;
        int count = n;
        
        for (int key : dict.keySet()) {
            dict.put(key, dict.get(key) - 1);
            count--; 
            
            if (count == 0) break;
        }

        if (count == 0) {
            return nums.length / 2; 
        } else {
            return n - count;
        }
    }
}

 

 

복습 1 풀이 (6/7)

[문제]
N마리 폰켓몬 중 N/2마리를 가져가야 한다. 
폰켓몬은 종류에 따라 번호를 붙여 구분한다. 
같은 종류의 폰켓몬은 같은 번호를 가진다. 

최대한 다양한 종류의 폰켓몬을 N/2마리 선택하는 방법을 찾아 그 때의 폰켓몬 종류의 개수를 반환 

[풀이]
1. 딕셔너리에 nums 넣기 (<int, int> key = 폰켓몬 종류, value = 개수)
2. n/2번 반복하며 딕셔너리의 값들을 하나씩 읽고 answer++
3. answer 출력 

 

 

코드 - 정답 

public int solution(int[] nums) 
{
    Dictionary<int, int> dict = new Dictionary<int, int>();
    foreach(int num in nums)
    {
        if(!dict.ContainsKey(num))
            dict.Add(num, 1);
        else
            dict[num]++;
    }

    int n = nums.Length / 2; 
    int answer = 0; 

    foreach(int key in dict.Keys)
    {
        answer++;
        if(answer > n) 
        {
            answer--;
            break;
        }
    }

    return answer;
}

 

기존에 내가 작성한 코드를 보니, 예전에는 dict[key]--, dict의 value값을 수정해주고 있었다. 

이건 굳이 하지 않아도 되는 계산이다. 

종류의 개수를 헤아리는 것만 하면 되므로, answer만 늘리는 방식으로 짠 현재 코드가 더 괜찮은 것 같다.