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 하면 됩니다.
입출력 예
| nums | result |
|---|---|
| [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입니다.
2. 풀이
문제가 길어서 처음에는 풀기 싫었는데 문제를 읽어보면 요구하는 바는 다음과 같이 간략하다는 것을 알 수 있다.
- 숫자 배열
nums가 주어지고, 여기서nums.length/2(이하N/2)개를 선택해야함 - 단, 최대한 다양한 숫자를 선택해야 하고, 그 개수를
return!
이를 바탕으로 내가 작성한 코드는 다음과 같다.
- 선택해야 하는 숫자의 개수를
max라는 이름으로 저장 - 배열
nums에서 중복을 제거했을 때 배열 길이를no_dup으로 저장 no_dup의 길이가max이상이라면max를 return, 아니라면np_dup을 return
function solution(nums) {
let max = nums.length / 2;
let no_dup = [...new Set(nums)].length;
return no_dup >= max ? max : no_dup;
}3. 공부한 내용
이전까지 배열에서 중복을 제거하는 방법으로 map과 includes를 사용해서 배열에 특정 값이 포함되어 있는지 여부를 검사하는 방식을 사용했다.
하지만 찾아보니 Set을 사용하는 방법이 있어서 이번 풀이에서 적용했다.
JavaScript의 배열에서 중복되는 값을 제거하는 방법이 여러 개가 있어서 정리를 해보려고 한다.
Set
const dupArr = [1, 2, 3, 1, 2];
const set = new Set(dupArr);
const uniqueArr = [...set];
document.writeIn(Array.isArray(uniqueArr)); // true
document.writeIn(uniqueArr); // 1,2,3const set = new Set(dupArr);- 중복값이 있는 배열을 Set 객체로 만들어서 중복을 제거한 후,
- 중복값이 있는 배열을 Set 객체로 만들어서 중복을 제거한 후,
const uniqueArr = [...set];- Spread Operator(전개연산자)를 사용하여 Set 객체를 다시 배열로 변환
- Set 객체를 배열로 변환할 때, Spread Operator 대신
Array.from()또는forEach()문을 사용할 수 있음
indexOf(), filter()
index(): 배열에서 특정 값이 처음으로 나타나는 index 리턴filter(): 특정 조건에 부합하는 배열의 모든 값을 배열 형태로 리턴
const dupArr = [1, 2, 3, 1, 2];
const uniqueArr = dupArr.filter((element, index) => {
return dupArr.indexOf(element) === index;
});
document.writeln(Array.isArray(uniqueArr)); // true
document.writeIn(uniqueArr); // 1,2,3dupArr.filter(callback);filter()함수는dupArr의 원소들을 callback 함수로 전달하여 각 원소들이 callback 함수에 정의된 기준에 부합하는지 검사하고, 검사 결과가 true를 리턴하는 원소들을 모아서 배열 형태로 리턴
dupArr.indexOf(element) === index;filter()함수로 전달된 callback 함수는 검사하고 있는 값(element)이 배열(dupArr)에서 가장 처음으로 나타나는 index와 검사하고 있는 원소의 index와 비교하여 같은 경우에만 true 리턴- 따라서 중복되는 값이 첫 번째로 나타나는 경우에만
filter()함수에서 걸러짐
forEach(), includes()
forEach(): 주어진 배열을 순회하면서, 배열의 원소들로 주어진 callback함수를 실행includes(): 주어진 배열에 특정 값이 포함되어 있는지 여부를 검사
const dupArr = [1, 2, 3, 1, 2];
let uniqueArr = [];
dupArr.forEach((element) => {
if (!uniqueArr.includes(element)) {
uniqueArr.push(element);
}
});
document.writeln(Array.isArray(uniqueArr)); // true
document.writeIn(uniqueArr); // 1,2,3dupArr.forEach(callback);dupArr(중복이 있는 배열)을 순회하면서
if (!uniqueArr.includes(element))uniqueArr(중복이 없는 배열)이 배열의 원소를 가지고 있지 않다면
uniqueArr.push(element)uniqueArr에 배열의 원소를 집어 넣음
참고
