소요시간 1시간 30분
알고리즘 기초공부와 기초문제를 풀면서 알아낸 것은 문제를 풀 때 효율이나 푸는 과정도 중요하지만
그 반례를 찾는것도 굉장히 중요하다고 생각이 들었습니다.
예전에는 정보를 주지않아서 불만 이였으나 이게 코딩테스트 문제를 푸는 방식중 하나 였던 것 같습니다.
이렇게 이야기를 하는 이유는 오늘도 반례를 찾는데 굉장히 오랜 시간이 걸렸고
생각보다 간단 했으며 문제에는 따로 조건이 없었는데 그걸 놓쳐서 오래 걸린 것 같습니다.
길이를 보면 무조건 이중 for문은 안되겠다는 생각이 들었으며
Lv2의 단계에서 이렇게 나온 문제는 보통 stack이나 queue 자료구조를 통해 무조건 For문을 한번씩 돌려야
문제가 해결된 다는 것을 알았습니다.
리스트를 한번씩 순회하면서 종류가 있다면 +1 해주어 종류별로 몇개있는지 알아내고 정렬하여
K를 그리드 알고리즘으로 빼주면 됩니다.
package Question;
import java.util.*;
/**
* 프로그래머스 귤 고르기
* */
public class PickingTangerines {
public static void main(String[] args) {
System.out.println(solution(6, new int[]{1, 3, 2, 5, 4, 5, 2, 3}));
System.out.println(solution(2, new int[]{1, 1, 1, 1, 2, 2, 2, 3}));
System.out.println(solution(5, new int[]{1, 1, 1, 1, 2, 2, 2, 3, 12, 34, 55554, 333434, 122, 3,2,3,2}));
System.out.println(solution(1, new int[]{1, 1, 1, 1, 2, 2, 2, 3, 3, 2, 3, 2}));
System.out.println(solution(9, new int[]{10000000,2,3,4,5,6,3,2,3,2,2,2,2,3,4,5,5}));
System.out.println(solution(9, new int[]{1,3,1,1,1,5,5,5,1,1,1,1,1,1,2,3,3}));
}
public static int solution(int k, int[] tangerine) {
int answer = 0;
HashMap<Integer, Integer> key = new HashMap<>();
// 종류별로 분류
for (int i : tangerine){
if(key.isEmpty()){
key.put(i,1);
}else if (key.containsKey(i)){
int add = key.get(i)+1;
key.put(i, add);
}else {
key.put(i,1);
}
}
System.out.println(key);
List<Integer> keySet = new ArrayList<>(key.keySet());
// Value 값으로 내림차순 정렬
keySet.sort((o1, o2) -> key.get(o2).compareTo(key.get(o1)));
// Value 값으로 오름차순 정렬
// keySet.sort(new Comparator<Integer>() {
// @Override
// public int compare(Integer o1, Integer o2) {
// return key.get(o1).compareTo(key.get(o2));
// }
// });
for (Integer ke : keySet) {
System.out.print("Key : " + ke);
System.out.println(", Val : " + key.get(ke));
// 음수가 됐을때만 뺄셈을 시도
if(k > 0){
k -= key.get(ke);
answer++;
}
}
return answer;
}
}
