코딩테스트 준비 - 폰켓몬

혼자서 다시푸는 코딩테스트 준비 일지 - 1

코딩테스트복습

Jul 19

8 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : Programmers
문제 : 폰켓몬
사용언어 : C++
난이도 : 극하 ( Lv 0.5 )
풀이시간 : 10m 미만
유형 : 해시?

문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 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 하면 됩니다.

입출력 예

numsresult[3,1,2,3]2[3,3,3,2,2,4]3[3,3,3,2,2,2]2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

문제 풀이 접근

이 문제는, 별다른 풀이가 필요없는 문제고, 하나의 개념만 알면 된다고 생각한다.
N 개의 갯수를 가진 nums 데이터가 들어오는데, 여기서 최대 몇가지를 뽑을 수 있는지라는 것인데, 예를 들면, nums.size = 4인 데이터가 1,2,3,4 로 구성되어 있으면 최대로 많이 뽑을 수 있는 구성은 (1,2),(2,3),(3,4),(4,1) 와 같은 같은 종류를 뽑는 구성밖에 없다. 이럴 경우 최대 종류수는 2개이다.
하지만, 1,2,3,4 와 같이 데이터가 다양하지 않은 경우도 있을 것이다. 1,1,1,1 와 같은 경우다.
이런 경우는, 아무리 뽑아도 자리의 순서만 다를뿐 결국 뽑는 종류는 (1,1) 1종류 밖에 못뽑는다.

그럼 개념은 잡힌것 같고, 이 두가지 케이스를 가지고 연산하면 된다.
최대로 내가 뽑을 수 있는 가짓수가 몇개 인지 리스트에 담는다.
있다면 담을 필요 없고, 없으면 담는다. 이 리스트의 size()는 결국 최대 뽑을 수 있는 가짓 수가 된다.
그리고, 내가 뽑을 수 있는 drawCount = N*0.5f 는 종류보다 많다면, 최대로 뽑을 수 있는 종류를 Answer에 넣어서 ret 한다.

왜? 앞에 말했듯이, 내가 1,1,1,1 에서 (1, ?) 뽑았다고 할때, drawCount가 하나 있다고 해도, 결국 내가 뽑을 수 있는 선택지는(1,1)이다. 결국 내가 뽑은것에서 가질 수 있는 최대 종류의 수는 1이다.
그렇기 때문에 종류가 drawCount 보다 작다면 drawCount 는 결국 몇백번을 뽑던 종류의 보다 많이 뽑을 수 없다. 이 상황에서 결국 최대값은 종류의 수와 다르지 않다.

정답 작성 코드 (C++) - 문제가 C# 지원 안한다.

#include <algorithm>
#include <list>
#include <iostream>

using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    list<int> lt;
    std::list<int>::iterator it;
    
    for(int i = 0; i < nums.size(); ++i)
    {
        int element = nums[i];
        it = std::find(lt.begin(),lt.end(),element);
        if(it == lt.end())
        {
            lt.push_back(element);
        }
    }
    
    int drawCount = nums.size() * 0.5f;
    
    if(drawCount > lt.size())
        answer = lt.size();
    else
        answer = drawCount;
    
    return answer;
}

코드 결과