코딩테스트 (1) - 폰켓몬
코딩테스트 문제 풀이
서론
저번 게시글에서 코딩테스트에 대해서 알아보고 매우 쉬운 문제를 풀어보았다.
오늘은 프로그래머스 1단계 문제 중 폰켓몬이라는 문제를 풀어보자.
문제 설명
당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 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 하면 됩니다.
풀이
첫번째로 내가 한 풀이부터 적겠다.
풀고보니 매우 비효율적이고 세련되지 못한 방식으로 문제를 해결해버렸다.
그래도 이것또한 공부라고 생각하고 풀이를 적어보겠다.
- 폰켓몬 번호마다 개수를 배열에 저장한다.
- 개수가 0인 폰켓몬 번호를 제외한 나머지 폰켓몬을 따로 배열에 담는다.
- 최대 개수를 따로 변수로 저장해둔다
- 1부터 최대 개수 n까지 그 배열을 검사한다.
- 검사한 개수와 일치하는 배열값이 나오면 그 값을 따로 배열에 저장한다.
- Count 값을 1 올리고 값을 따로 저장한 배열과 검사해 중복된 것인지를 검사한다.
- 중복된 값이 아니라면 answer의 값을 1 올리고 다음 검사로 넘어간다.
- 위 과정을 Count가 최대 가질 수 있는 폰켓몬 수와 같아질때까지 반복한다.
안다. 말하지 않아도 이게 무슨 말인가 이해조차 어려운 엉상한 방법이다.
아직 이런 문제에 대해서 세련되게 풀지못하니 공부가 부족한 것 같다.
일단 아래 코드를 보면서 하나하나 풀이를 해보겠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function solution(nums) {
const maxPonkemon = 200000; // 최대 폰켓몬 번호
let canGetPonkemon = nums.length/2; // 가질 수 있는 폰켓몬 개수
let numsCount = []; // 폰켓몬 번호에 따른 개수를 저장할 배열
let answer=0; // 최대 가질 수 있는 폰켓몬 종류 수
let maxPonkemonNum = 0; // 폰켓몬 종류 중 가장 높은 번호를 가진 폰켓몬
let getPonkemon = []; // 최대 가질 수 있는 폰켓몬으로 가질 때의 폰켓몬 종류를 저장
for(let i = 0; i<maxPonkemon; i++){
numsCount.push(0); // 폰켓몬 종류마다 개수를 저장하기 위해 무려 20만개의 배열을 생성.....ㅋㅋㅋㅋㅋㅋㅋ
}
// 전체 배열을 돌며 무려 20만개의 폰켓몬 종류가 있는지 없는지 검사
// 있다면 그 번호에 해당하는 배열의 값에 1을 더한다
for(let i = 0; i<nums.length; i++){
for(let j=0;j<=maxPonkemon;j++){
if(nums[i]==j+1){
numsCount[j]++;
if(j+1 > maxPonkemonNum) maxPonkemonNum = j+1;
break;
}
}
}
let maxPonkemonCount = 0; // 가지고 있는 가장 많은 폰켓몬 종류의 개수
let buff = []; // 유효한 폰켓몬의 개수만을 따로 저장할 배열
// 0개가 아닌 폰켓몬을 걸러내는 반복문
for(let i = 0; i < maxPonkemonNum; i++){
if(numsCount[i] !== 0) buff.push(numsCount[i])
if(numsCount[i] > maxPonkemonCount) maxPonkemonCount = numsCount[i];
}
let count = 0; // 가지고 간 폰켓몬의 개수
// 가실 수 있는 폰켓몬 만큼 가져갈 때까지 반복문을 굴림
// 폰켓몬 중 가장 적은 수부터 검사하여 가장 많은 수 까지 반복문을 굴림
// 가져간 폰켓몬의 개수를 배열에서 -1 하고 count가 목표치에 도달할때까지 반복
// 가져간 폰켓몬과 중복됐는지 검사하고 중복되지 않았다면 answer에 +1
while(count < canGetPonkemon){
for(let j = 1; j<=maxPonkemonCount; j++){
for(let i =0; i<=buff.length; i++){
if(count >= canGetPonkemon){
return answer; // count가 목표치에 도달하면 값을 return
}
if(buff[i]===j){
let check = 0;
count++;
// 중복된 폰켓몬이 있는지를 검사
for(let k = 0; k<getPonkemon.length; k++){
if(getPonkemon[k] === i){
check = 1;
}
}
getPonkemon.push(i);
if(check === 0) answer++;
numsCount[i]--;
}
}
}
}
}
이런 무식한 방법으로 문제를 푸는 사람이 나말고 또 있을지 모르겠다…
사실 내 풀이 방법은 틀렸다고 보는 것이 맞다.
일단 기대값이 나오고, 기준으로 정한 시간내에 겨우겨우 아슬아슬하게 통과했지만 위의 풀이는 면접관들 입장에서는 틀린 답일 것이다.
그리고 문제의 통과기준이 10000ms 인데 난 9410ms가 최고기록으로 걸렸다.
아무래도 수많은 반복문과 말도 안되는 경우 수들까지 모두 계산하려는 내 무지가 만든 결과가 아닌가 싶다.
그렇다면 다른 똑똑한 사람들이 푼 세련된 답은 어떤지보고 그 답에 대한 풀이를 같이 해보자.
1
2
3
4
5
6
function solution(nums) {
const max = nums.length / 2;
const arr = [...new Set(nums)];
return arr.length > max ? max : arr.length
}
우와 이게뭐야?
내가 처음 위의 코드를 보고 생각한 말이다.
보면 정말 간단한 방법인데 저걸 생각못하다니 아직 갈길이 먼 것 같다.
위의 코드를 이해하려면 new Set() 이라는 것에 대해 알아야할 것 같다.
그냥 간단하다.
배열에서 중복된 값을 제거하고 중복되지 않은 값만으로 새로운 배열을 만들어주는 함수이다.
거두절미하고 위의 코드에 대한 풀이를 해보자.
- max에 가져갈 수 있는 최대 폰켓몬 개수를 저장한다.
- arr에 nums에서 중복된 값을 제거하는 Set 함수를 이용해 새로운 배열을 만든다.
- 중복을 제거하게되면 종류가 다른 폰켓몬들만 남게된다.
- 중복된 값이 제거된 배열의 길이와 최대 가져갈 수 있는 폰켓몬 개수 max를 비교한다.
- 왜? arr의 길이가 max보다 길다면 최대 가져갈 수 있는 폰켓몬 개수를 초과한 것이기때문에 가져갈 수 있는 종류는 max개가 된다.
저런 코딩을 할 줄 알아야하는데 배열에서 왜 중복된 값을 제거할 생각을 못하고 그걸 밥알 세듯 하나하나 세고있엇는지 모르겠다.
마치며
아무튼 오늘은 코딩테스트 1단계 첫문제 폰켓몬을 풀어보았다.
직접 코딩테스트를 해보니 내가 생각한 것보다 시간도 오래걸리고 내가 생각한 방식이 너무 비효율적이라 좌절을 겪은 것 같다.
그러나 이것또한 공부라고 생각하고 내일을 위한 발판으로 삼아 나아가야겠다.