출처: https://school.programmers.co.kr/learn/courses/30/lessons/138476
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
1 ≤ k ≤ tangerine의 길이 ≤ 100,000
1 ≤ tangerine의 원소 ≤ 10,000,000
입출력 예
k tangerine result
6 [1, 3, 2, 5, 4, 5, 2, 3] 3
4 [1, 3, 2, 5, 4, 5, 2, 3] 2
2 [1, 1, 1, 1, 2, 2, 2, 3] 1
입출력 예 설명
입출력 예 #1
본문에서 설명한 예시입니다.
입출력 예 #2
경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.
입출력 예 #3
경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.
내가 30분이내로 작성한 코드다.
문제에대한 이해는 됐는데
뭔가 시간을 더 투자 했으면 풀수 있었으면 하는 맘도 들긴하다.
최솟값을 어떻게 비교해서 반환 해낼까? 그게 잘 안되었던거 같다.
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer = 0;
// 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다.
// 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다
// 귤의 크기의 종류 반환 (최솟값)
// case 1
// 1, 4 제외한 나머지 6개뽑을시 -> 2반환
// case 2
// 3, 5 2개씩 뽑을시 -> 2 반환
// 2, 3 2개씩 뽑을시 -> 2 반환
// 2, 5 2개씩 뽑을시 -> 2 반환
// case 3
// 1 2개, 2 2개 뽑을시 -> 1반환
int arr[] = new int[k];// k크기만큼의 배열 사이즈
int min = 100000;// 원소 종류 세기
int count = 0;
// tangerine 배열에서 뽑는다
while(true){// 최솟값이 나올때 break
for(int i = 0; i < k; i++){//k갯수만큼 랜덤으로 뽑아서(중복가능) arr 배열에 저장
Random rand = new Random();
int randomIdx = rand.nextInt(tangerine.length);
arr[i] = tangerine[randomIdx];
}
// arr[i] 중복 판별
Set<Integer> numSet = new HashSet<>();
// 저장 시키기 향상 for문
for(int num : numSet){
numSet.add(num);
}
min = numSet.size();
Math.min(count, min);
}
return min;
}}
지금 작성한 방식은 랜덤하게 k개를 뽑아서 종류 수를 구하는 무작위 시뮬레이션 방식인데, 이건 문제의 의도와는 맞지 않은거 같다.
-
귤 크기별 개수를 센다.
-
많이 나오는 크기부터 선택한다.
-
총 k개가 될 때까지 종류를 늘려가며 고른다.
-
이때 사용된 크기 종류 수가 정답!
이렇게 되어야 함.
위 요구 사항을 반영한 코드문이다.
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
Map<Integer, Integer> countMap = new HashMap<>();
// 1. 귤 크기별 개수 세기
for (int size : tangerine) {
countMap.put(size, countMap.getOrDefault(size, 0) + 1);
}
// 2. 크기별 개수를 큰 순서로 정렬
List<Integer> counts = new ArrayList<>(countMap.values());
counts.sort(Collections.reverseOrder());
// 3. 많이 나오는 크기부터 고르기
int answer = 0;
int total = 0;
for (int cnt : counts) {
total += cnt;
answer++;
if (total >= k) break;
}
return answer;
}}
맵을 활용하여 크기별 개수를 세고,
개수 큰 순서대로 정렬했다.
맨 마지막 반복문은
정렬된 counts 리스트(= 귤 크기별 개수)를 많이 나온 순서대로 하나씩 보면서,
얼마나 많은 귤을 골랐는지 누적하고 (total += cnt)
몇 가지 크기를 사용했는지 센다. (answer++)
k개 이상을 고르면 종료합니다.
그외에.. 다른분들 풀이
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer = 0;
int[] arr = new int[10000001];
for(int i = 0; i < tangerine.length; i++) {
int num = ++arr[tangerine[i]];
}
Arrays.sort(arr);
int sum = 0;
for(int i = arr.length-1; i >= 0; i--) {
sum += arr[i];
answer++;
if(sum >= k) break;
}
return answer;
}}
