[프로그래머스] JavaScript Lv1 - 폰켓몬(42840)

개요

문제 이름: 폰켓몬 (1845)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1845
플랫폼: 프로그래머스
알고리즘 분류: 해시
소요 시간: 20분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

해당 문제는 배열에서 주어진 조건에 맞게 원소를 선택하여 최대한 많은 종류의 원소를 포함하도록 하는 알고리즘 문제입니다. 이를 해결하기 위해서는 '해시(Hash) 알고리즘'을 활용할 수 있습니다.

 

해시 알고리즘이란 키(key)와 값(value)을 매핑하여 데이터를 저장하고 검색하는 알고리즘입니다. 해시 함수를 사용하여 키를 해시값으로 변환하고, 이를 인덱스로 사용하여 데이터에 접근합니다. 해시 알고리즘을 사용하면 데이터의 중복을 효율적으로 제거하고 빠른 검색이 가능합니다.

 

이 문제에서는 JavaScript의 Set 객체를 활용하여 해시 알고리즘을 구현할 수 있습니다. Set은 값의 집합으로, 각 값은 고유하며 중복을 허용하지 않습니다. 따라서 배열의 원소들을 Set에 추가하면 자동으로 중복이 제거되어 원소의 종류 수를 파악할 수 있습니다.

 

문제 해결을 위해 먼저 Set을 사용하여 배열의 중복을 제거합니다. 그 다음 두 가지 경우를 고려합니다.

1. Set의 크기(원소 종류 수)가 선택해야 할 원소의 수(N/2)보다 크거나 같은 경우: 이때는 N/2개를 선택하더라도 모두 다른 종류의 원소가 선택될 수 있으므로 정답은 N/2입니다.
2. Set의 크기가 N/2보다 작은 경우: 이때는 원소 종류 수만큼만 선택하는 것이 최대이고, 그 이상 선택하면 중복된 원소가 생기므로 정답은 원소 종류 수가 됩니다.

이를 바탕으로 Set의 size 속성과 배열의 길이를 비교하여 작은 값을 리턴하면 문제를 해결할 수 있습니다.

 

시도

1차 시도  (성공)

function solution(nums) {
    let answer = 0;
    let hashSet = new Set(nums);
    let numsLen = nums.length/2;

    if (hashSet.size > numsLen) {
        answer = numsLen
    }
    else {
        answer = hashSet.size
    }
    return answer;
}

처음에는 Set을 이용해 nums 배열의 중복을 제거한 뒤, Set의 size와 nums 배열 길이의 절반 값을 비교하여 조건에 따라 answer에 할당하는 방식으로 구현했습니다. 코드는 잘 동작하지만 if-else 구문이 들어가는 바람에 다소 길어졌습니다.

 

2차 시도  (성공)

function solution(nums) {
	let hashSet = new Set(nums);
	return Math.min(hashSet.size, nums.length / 2);
}

1차 시도를 조금 더 간결하게 리팩토링한 코드입니다. Set의 size와 배열 길이의 절반 중 작은 값을 바로 리턴하도록 했습니다. 조건문 없이도 문제의 조건을 잘 반영할 수 있었습니다.

 

3차 시도 (성공)

function solution(nums) {
	return Math.min(new Set(nums).size, nums.length / 2);
}

2차 시도에서 불필요한 변수 선언을 없앴습니다. Set 객체를 바로 생성하여 size를 가져오고, 배열 길이의 절반과 비교해 작은 값을 리턴했습니다. 한 줄로 간단명료하게 문제를 해결할 수 있었습니다.

 

사족

이 문제는 해시 알고리즘에 대한 이해와 Set 자료구조를 활용하는 능력이 중요한 문제였습니다.

해시 알고리즘을 사용하여 중복을 제거하고 원소의 종류 수를 파악한 후, 문제에서 요구하는 조건에 맞게 적절한 값을 리턴하는 것이 핵심이었습니다.

문제 풀이를 진행하면서 불필요한 부분을 제거하고 코드를 간결하게 만들어가는 과정도 중요한 경험이 된 것 같습니다.