[프로그래머스] JavaScript Lv2 - 귤 고르기(138476)

개요

문제 이름: 귤 고르기 (138476)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/138476
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 1시간

 

문제 전문

설명

제한사항

입출력

 

 

문제 풀이

해설

이 문제는 귤의 크기별 개수를 파악하여, 최소한의 종류로 k개의 귤을 고르는 문제입니다. 문제 해결을 위해 먼저 귤의 크기별 개수를 파악하고, 개수가 많은 순서대로 귤을 고르는 그리디 알고리즘을 적용할 수 있습니다.

 

문제 접근 방식은 다음과 같습니다.

1. 귤의 크기별 개수를 파악하기 위해 객체(sizeCount)를 생성합니다.
2. 주어진 배열(tangerine)을 순회하면서 각 크기의 귤이 몇 개 있는지 객체에 저장합니다.
3. 객체의 값(귤의 개수)을 배열로 변환하고, 내림차순으로 정렬합니다.
4. 정렬된 배열을 순회하면서 k개 이상의 귤을 고를 때까지 귤의 종류 수(kindCount)를 증가시킵니다.
5. 필요한 귤의 개수(k)를 채우면 반복을 중단하고, 최종적으로 선택된 귤의 종류 수(kindCount)를 반환합니다.

이렇게 문제를 해결하면 귤의 크기별 개수를 파악하고, 개수가 많은 순서대로 귤을 고르게 되므로 최소한의 종류로 k개의 귤을 선택할 수 있습니다.

 

그리디 알고리즘

그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는 데에 사용되는 알고리즘 중 하나입니다. 그리디 알고리즘은 문제를 해결하는 과정에서 현재 상태에서 가장 최선의 선택을 하는 방식으로 진행합니다. 즉, 각 단계에서 가장 좋아 보이는 선택을 하면서 최종적인 해답에 도달하는 것이 그리디 알고리즘의 기본 아이디어입니다.

 

그리디 알고리즘은 일반적으로 다음과 같은 과정으로 문제를 해결합니다.

1. 해결하고자 하는 문제에서 최적의 해를 구성하는 요소들을 선택합니다.
2. 현재 상태에서 가장 좋아 보이는 선택을 합니다.
3. 선택한 요소를 해결책에 추가합니다.
4. 문제가 해결될 때까지 위 과정을 반복합니다.

그리디 알고리즘은 각 단계에서 최선의 선택을 하기 때문에, 전체적인 관점에서는 최적의 해를 보장하지 않을 수 있습니다. 하지만 특정 문제에서는 그리디 알고리즘으로 최적해를 얻을 수 있습니다.

 

이번 문제에서는 그리디 알고리즘을 다음과 같이 적용할 수 있습니다.

1. 귤의 크기별 개수를 파악합니다. 이를 통해 어떤 크기의 귤이 가장 많이 있는지 알 수 있습니다.
2. 귤의 개수가 많은 순서대로 귤을 선택합니다. 이는 현재 상태에서 가장 좋아 보이는 선택입니다.
3. 선택한 귤의 개수를 k개가 될 때까지 누적합니다.
4. 선택한 귤의 종류 수를 최종 해답으로 제시합니다.

이렇게 그리디 알고리즘을 적용하여 문제를 해결하면, 최소한의 종류로 k개의 귤을 고를 수 있습니다. 각 단계에서는 가장 개수가 많은 귤을 선택하는 것이 최선의 선택이 되며, 이를 통해 전체적으로 최소한의 종류를 선택할 수 있게 됩니다.

 

시도

1차 시도  (성공)

// 1차 시도 (성공)
function solution(k, tangerine) {
	// 귤의 크기별 개수를 저장할 객체 생성
	let sizeCount = {};

	// 귤의 크기별 개수 계산
	for (let size of tangerine) {
		if (sizeCount[size]) {
			sizeCount[size] += 1;
		} else {
			sizeCount[size] = 1;
		}
	}

	// 개수를 기준으로 내림차순 정렬
	let sortedCounts = Object.values(sizeCount).sort((a, b) => b - a);

	// 필요한 개수(k)를 채우기 위한 변수 초기화
	let sum = 0;
	let kindCount = 0;

	// 필요한 개수(k)를 채울 때까지 큰 그룹부터 선택
	for (let count of sortedCounts) {
		sum += count;
		kindCount += 1;

		// 필요한 개수를 채웠다면 반복 중단
		if (sum >= k) {
			break;
		}
	}

	// 결과 반환
	return kindCount;
}

 

코드 설명은 다음과 같습니다.

1. sizeCount 객체를 생성하여 귤의 크기별 개수를 저장합니다.
2. tangerine 배열을 순회하면서 각 크기의 귤이 몇 개 있는지 sizeCount 객체에 저장합니다.
   1. 해당 크기의 귤이 이미 객체에 존재하면 개수를 1 증가시킵니다.
   2. 해당 크기의 귤이 객체에 존재하지 않으면 새로운 속성으로 추가하고 개수를 1로 초기화합니다.
3. Object.values() 메서드를 사용하여 sizeCount 객체의 값(귤의 개수)들을 배열로 변환합니다.
   1. sort() 메서드를 사용하여 배열을 내림차순으로 정렬합니다.
4. 정렬된 배열을 순회하면서 필요한 개수(k)를 채울 때까지 반복합니다.
   1. sum 변수에 현재 귤의 개수를 누적합니다.
   2. kindCount 변수를 1 증가시켜 선택한 귤의 종류 수를 카운트합니다.
   3. 누적 합(sum)이 필요한 개수(k) 이상이 되면 반복을 중단합니다.
5. 최종적으로 선택된 귤의 종류 수(kindCount)를 반환합니다.

 

사용된 주요 메서드

• Object.values(): 객체의 값들을 배열로 반환합니다.
• sort(): 배열을 정렬합니다. 매개변수로 비교 함수를 전달할 수 있습니다.
  • (a, b) => b - a: 내림차순 정렬을 위한 비교 함수입니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n log n)
  여기서 n은 tangerine 배열의 길이입니다. 귤의 크기별 개수를 계산하는데 O(n)의 시간이 소요되고, 귤의 개수를 정렬하는데 O(n log n)의 시간이 소요됩니다.
• 공간 복잡도: O(n)
  여기서 n은 귤의 고유한 크기의 개수입니다. 귤의 크기별 개수를 저장하는 객체(sizeCount)와 정렬된 귤의 개수를 저장하는 배열(sortedCounts)이 추가로 사용됩니다.