(Java) 프로그래머스 더 맵게

처음 문제를 읽고 리스트로 풀려고 했었다.

while 안에서 매번 정렬을 한 뒤 첫번째 두번째 값을 꺼내면 될것이라고 생각했는데

테스트 케이스를 통과를 못했다.

정렬을 계속 해주는것 때문인가...

 

생각해보니 큐로도 풀 수 있을것 같아서 검색해보니 우선순위 큐라는것을 알게 되었고 이를 힙이라는 자료 구조를 가지고 구현하는 것이었다. 한번에 명쾌하게 이해되지는 않는 개념이어서 다시 공부해 봐야겠다.

 

---

처음 작성한 코드 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MoreHot {
	public static void main(String[] args) {
		int[] scoville = {1, 2, 3, 9, 10, 12};
		int k = 7;
		int answer = 0;
		
		// 리스트 선언 후 배열 변환
		List<Integer> list = new ArrayList();
		
		for(int i : scoville) {
			list.add(i);
		}
		
		while(!(list.get(0) >= k)) {
			Collections.sort(list);
			int temp = mix(list.get(0), list.get(1));
			list.remove(0);
			list.remove(0);
			list.add(temp);
			answer++;
		}
		System.out.println(answer);
		System.out.println(list);
		
	}
	
	// 섞는 함수 만들기
	static int mix(int a, int b) {
		return a + (b * 2);
	}
	
}

 

최종 코드

import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int solution(int[] scoville, int K) {
        		int answer = 0;
		int min = scoville[0];
		
		// 리스트 선언 후 배열 변환
		Queue<Integer> list = new PriorityQueue();
		
		for(int i : scoville) {
			list.add(i);
		}
		
		while(list.peek() <= K) {
            if(list.size() < 2) return -1;
			int temp = mix(list.poll(), list.poll());
			list.add(temp);
			answer++;
            
		}
		return answer;
	}
	
	// 섞는 함수 만들기
	static int mix(int a, int b) {
		return a + (b * 2);
	}
}