[프로그래머스] 더 맵게

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게 | 프로그래머스

코드

	// 모든 scoville이 K이상일때까지 
	// K보다 작은 scoville이 하나라도 존재한다면 -1을 반환한다.
	public static int solution(int[] scoville, int K) {

		//들어온 순서에 상관없이 우선순위대로 나간다.
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		Arrays.sort(scoville);

		// 정렬 된 최초 scoville에서 K보다 작은수만 priorityQueue에 add한다.
		for ( int n : scoville ) {
			pq.add(n);
		}
		
		int cnt = 0 ;

		// K이상의 수가 첫번째에 나온다면 더이상 회전 할 필요가 없다.
		// K미만의 수는 모두 봐야한다.
		while ( pq.peek() < K ) {
			
			if(pq.size()==1) return -1;

			cnt++;

			//priorityQueue는 우선순위에 따라 데이터를 뽑는다.
			int newScoville = pq.poll() + pq.poll()*2 ;
			
			// [ 1,1,2 ] , K=3 과같은경우 원래2는빠질 수 있는데 남아있게 되는 경우가존재해서 크거나 같은경우도 add를 해주어야한다.
			pq.add(newScoville);
		}
		return cnt;
	}//solution

제출 결과

후기

처음에는, K보다 작은 수를 List에 담은 후, remove(0) , remove(0)으로 앞의 2개 데이터를 삭제, 재계산한 scoville 중 작은 값만 add 하고 add 된 List를 sort()하는 방법을 선택해보았다.

 

효율성도 떨어지고, 문제도 조건을 정확히 고려하지 못하였다.

 

priorityQueue를 사용한다는 풀이를 보고 적용해보았다.

 

priorityQueue의 장점은 add된 데이터의 순서에 상관없이 우선순위에 따라 데이터를 poll 할 수 있다는 점이다.

 

priorityQueue를 활용하여 해결한 나의 풀이이다.

 

1. 최초 입력배열 scoville을 모두 priorityQueue에 넣어준다.

 

2. priorityQueue의 데이터의 첫 번째 우선순위가 K미만의 수가 계속 존재할 때까지 데이터를 2개씩 빼가면서 새로운 scoville을 계산하고 add 해주고 하는 작업을 반복한다.

 

* 처음에 재계산된 scoville을 add하는 대상을 K미만의 수일 때만 add 해 주었더니 테스트 케이스 6,7,10,13번만 실패했다.

 

문제는 [ 1,1,2 ] , K=3과 같은 데이터가 들어왔을때 1회전에 나온 결과 값 3이 add 되지 않기 때문에 K보다작은 2가 처리되지 않고 -1이 리턴되었기 때문이었다.

 

3을 add해서 [ 3,2 ]로 scoville을 재계산해서 2도 처리될 수 있게끔 해주어야 했다. ( 결국 답은 2회전 )

 

PriorityQueue라는 자료구조를 알면 쉽게 해결할 수 있는 문제인 것 같다. 몰랐다면 더 많은 고민을 했을 것이다..