문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/138476
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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가지로, 이 값이 최소가 됩니다.
풀이과정
Hashmap으로 개수 세어서 개수가 최소가 되는걸 골라야겠다고 생각함
→ 이거 전에 과일박스 문제랑 비슷하게 걍 array 정렬하면 될수도,
이번에는 값이 제일 나가는게 아니라 갯수가 제일 많은거 순으로 정렬해야돼서 안됨 ㅎㅎ
HashMap 정렬
HashMap Value 기준으로 정렬하기
⭐ comparator를 람다 함수로 구현하여 map 정렬하기
Map<String, Integer> map = new HashMap<>();
map.put("a", 3);
map.put("b", 2);
map.put("c", 1);
//정렬
List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(((o1, o2) -> map.get(o1.getKey()) - map.get(o2.getKey())));
//출력
for(Map.Entry<String, Integer> entry : entryList){
System.out.println("key : " + entry.getKey() + ", value : " + entry.getValue());
}
오오 제출함
제출 코드
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
class Solution {
public int solution(int k, int[] tangerine) {
HashMap<Integer, Integer> sizeCount = new HashMap<>();
for(int i : tangerine){
int count = sizeCount.getOrDefault(i,0);
count++;
sizeCount.put(i,count);
}
LinkedList<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(sizeCount.entrySet());
entryList.sort(((o1, o2) -> sizeCount.get(o2.getKey()) - sizeCount.get(o1.getKey())));
int full = 0;
int answer = 0;
for(Map.Entry<Integer, Integer> entry : entryList){
if(full>=k){
break;
}
full = full + entry.getValue();
answer++;
}
return answer;
}
}
코드 개선
근데 답안 제출하고 나서 생각해보니
key값을 아예 안 쓰고 있는데 저걸 왜 key값까지 넣어서 정렬해야하나 싶어서 코드 바꿔봄
1. LinkedList보단 ArrayList가 조회측면에서 더 빠르지 않나 싶어서 바꿔봄
LinkedList일때 실행 속도
ArrayList로 바꾼 후 실행 속도
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
public int solution(int k, int[] tangerine) {
HashMap<Integer, Integer> sizeCount = new HashMap<>();
for(int i : tangerine){
int count = sizeCount.getOrDefault(i,0);
count++;
sizeCount.put(i,count);
}
ArrayList<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(sizeCount.entrySet());
entryList.sort(((o1, o2) -> sizeCount.get(o2.getKey()) - sizeCount.get(o1.getKey())));
int full = 0;
int answer = 0;
for(Map.Entry<Integer, Integer> entry : entryList){
if(full>=k){
break;
}
full = full + entry.getValue();
answer++;
}
return answer;
}
}
역시 훨씬 빨라짐
2. Value만 있는 리스트로 만들어서 비교하면 더 빨라지나?
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
public int solution(int k, int[] tangerine) {
HashMap<Integer, Integer> sizeCount = new HashMap<>();
for(int i : tangerine){
int count = sizeCount.getOrDefault(i,0);
count++;
sizeCount.put(i,count);
}
ArrayList<Integer> entryList = new ArrayList<>(sizeCount.valueSet());
entryList.sort((o1,o2) -> o2 - o1);
int full = 0;
int answer = 0;
for(Integer entry : entryList){
if(full>=k){
break;
}
full = full + entry;
answer++;
}
return answer;
}
}
바꾸는중
/Solution.java:17: error: cannot find symbol
ArrayList<Integer> entryList = new ArrayList<>(sizeCount.valueSet());
^
symbol: method valueSet()
location: variable sizeCount of type HashMap<Integer,Integer>
1 error
⭐HashMap의 .entrySet()
map.entrySet()
map.keySet(), mep.get()
map.values()
valueSet()이 아니라 values() 였구만!!
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
public int solution(int k, int[] tangerine) {
HashMap<Integer, Integer> sizeCount = new HashMap<>();
for(int i : tangerine){
int count = sizeCount.getOrDefault(i,0);
count++;
sizeCount.put(i,count);
}
ArrayList<Integer> entryList = new ArrayList<>(sizeCount.values());
entryList.sort((o1,o2) -> o2 - o1);
int full = 0;
int answer = 0;
for(Integer entry : entryList){
if(full>=k){
break;
}
full = full + entry;
answer++;
}
return answer;
}
}
values로 해서 됐음!!
테스트 1 〉 통과 (30.21ms, 93.1MB)
| 테스트 2 〉 | 통과 (22.91ms, 95MB) |
| 테스트 3 〉 | 통과 (29.57ms, 97.4MB) |
| 테스트 4 〉 | 통과 (29.68ms, 86.3MB) |
| 테스트 5 〉 | 통과 (18.31ms, 82.9MB) |
| 테스트 6 〉 | 통과 (40.04ms, 78.2MB) |
| 테스트 7 〉 | 통과 (29.69ms, 87.4MB) |
| 테스트 8 〉 | 통과 (33.81ms, 97.3MB) |
| 테스트 9 〉 | 통과 (23.22ms, 98.2MB) |
| 테스트 10 〉 | 통과 (22.17ms, 87.2MB) |
| 테스트 11 〉 | 통과 (0.54ms, 74.4MB) |
| 테스트 12 〉 | 통과 (0.82ms, 71.8MB) |
| 테스트 13 〉 | 통과 (0.60ms, 74.5MB) |
| 테스트 14 〉 | 통과 (0.68ms, 76.2MB) |
| 테스트 15 〉 | 통과 (0.65ms, 71.9MB) |
| 테스트 16 〉 | 통과 (0.84ms, 78.5MB) |
| 테스트 17 〉 | 통과 (0.80ms, 74.2MB) |
| 테스트 18 〉 | 통과 (0.75ms, 78.2MB) |
| 테스트 19 〉 | 통과 (0.71ms, 77.3MB) |
| 테스트 20 〉 | 통과 (0.50ms, 81.1MB) |
| 테스트 21 〉 | 통과 (1.61ms, 76.9MB) |
| 테스트 22 〉 | 통과 (1.87ms, 74MB) |
| 테스트 23 〉 | 통과 (2.48ms, 79.6MB) |
| 테스트 24 〉 | 통과 (1.69ms, 73.3MB) |
| 테스트 25 〉 | 통과 (12.75ms, 78.7MB) |
| 테스트 26 〉 | 통과 (18.38ms, 87.9MB) |
| 테스트 27 〉 | 통과 (48.30ms, 103MB) |
| 테스트 28 〉 | 통과 (48.38ms, 97.6MB) |
| 테스트 29 〉 | 통과 (57.91ms, 96.1MB) |
| 테스트 30 〉 | 통과 (48.61ms, 96.6MB) |
| 테스트 31 〉 | 통과 (25.85ms, 81.7MB) |
| 테스트 32 〉 | 통과 (33.10ms, 97.1MB) |
| 테스트 33 〉 | 통과 (53.65ms, 95.3MB) |
| 테스트 34 〉 | 통과 (46.07ms, 90.5MB) |
오오 더 빨라짐!!
다른사람의 풀이
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer = 0;
HashMap<Integer,Integer> map =new HashMap<>();
for (int t : tangerine) {
map.put(t, map.getOrDefault(t, 0) + 1);
}
List<Integer> list = new ArrayList<>(map.keySet());
list.sort((o1, o2) -> map.get(o2)-map.get(o1));
for(Integer key:list){
k -=map.get(key);
answer++;
if(k<=0){
break;
}
}
return answer;
}
}오 나랑 거의 똑같이 풂
근데 이거 꿀팁이다
⭐map.put(t, map.getOrDefault(t, 0) + 1);
Collections.sort를 쓰는 사람도 있네 어차피 이번 문제는 map정렬 아니라 상관없지만 map정렬을 해야하면 collections.sort는 못씀
import java.util.*;
class Solution {
public int solution(int k, int[] tangerine) {
int answer = 0;
Comparator<Integer> c = (s1,s2)->s1.compareTo(s2);
//Key: 크기 , value: 갯수
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<tangerine.length;i++){
int count = map.getOrDefault(tangerine[i],0);
map.put(tangerine[i],count+1);
}
List<Integer> valueList = new ArrayList(map.values());
Collections.sort(valueList,Collections.reverseOrder());
for(int i=0;i<valueList.size();i++){
k-=valueList.get(i);
answer++;
if(k<=0){
break;
}
}
return answer;
}
}'Coding Test' 카테고리의 다른 글
| [프로그래머스] 연속 부분수열 (1) | 2024.02.29 |
|---|---|
| [프로그래머스] 괄호 회전하기 (0) | 2024.02.29 |
| [프로그래머스] 카펫 (1) | 2024.01.08 |
| [프로그래머스]피보나치 수 (1) | 2024.01.08 |
| [프로그래머스] JadenCase 문자열 만들기 (0) | 2024.01.08 |