<나의풀이>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.*; class Solution { public int solution(int[] scoville, int K) { int answer = 0; List<Integer> list = new ArrayList<>(); for(int n : scoville) list.add(n); int size = list.size(); while(size>1){ Collections.sort(list); if(list.get(0)<K){ list.add(list.get(0)+list.get(1)*2); list.remove(1); list.remove(0); size--; answer++; }else{ break; } } if(list.get(0)<K) return -1; return answer; } } | cs |
List를 이용하여 풀었지만 효율성에서 0점을 받았다. 정렬 때문에 통과 못할 걸 알고 있었지만 내가 아는 선에선 이렇게 풀 수 밖에 없었다.
찾아보니 우선순위 큐(힙)을 이용하여 푸는 문제였다.
- 값을 리스트로 받고 리스트 사이즈를 구한다.
- 사이즈가 1초과면 반복 시작.
- 정렬을 먼저하고 첫번째 요소가 K보다 작다면 첫요소와 두번째 요소를 이용하여 계산후 list에 추가. 이후 두번째 요소를 먼저 제거하고 첫번째 요소를 제거.
- 반복 완료 후 list의 첫요소가 k보다 작으면 -1 리턴. 아니면 answer리턴
<다른사람 풀이>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | import java.util.PriorityQueue; class Solution { public int solution(int[] scoville, int K) { int answer = 0; PriorityQueue<Integer> queue = new PriorityQueue<Integer>(scoville.length); for(int num : scoville) queue.add(num); while(queue.size()>1) { if(queue.peek()>=K) return answer; int least = queue.poll(); int second_least = queue.poll(); queue.add(least + (second_least * 2)); answer++; } if(queue.peek()<K) return -1; return answer; } } | cs |
우선순위 큐는 값을 넣으면 자동으로 힙구조로 정렬하여 저장이 된다. 힙 구조는 시간 복잡도가 O(logN)으로 매우 빠르다.
