더 맵게 / 프로그래머스 연습문제 / programmers / level2 / java / 힙

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

이번엔 처음으로 힙에 관련된 문제를 풀어보았다.

힙이 무어냐?..

힙은 특정한 규칙을 가지는 트리로, 힙을 이용해서 우선순위 큐를 구현할 수 있습니다.

많은 언어에서 이미 구현된 우선순위 큐 라이브러리를 제공합니다. 이를 활용하면 효율적으로 문제를 풀 수 있습니다. 우선순위 큐를 이용해서 해결하기에 적합한 문제들을 만나보세요.

라고 한다. 하여 자바 라이브러리에서 제공하는 큐라는 것을 배워 사용해보기로 했다.

 

스택을 한번 사용해보고 나니 이해하는데 그렇게 어렵지는 않았다.

기본적으로 큐는 FIFO인데 그거보다 1층 더 나아가서 트리, 힙 구조로 구성되어있는 우선순위 큐가 필요하다.

 

이번 문제는 주어진 스코빌지수 보다 같거나 낮을때까지 계산을 반복해서 해 주어야하기 때문에 배열에서 가장 낮은 숫자가 계속적으로 필요하기 때문이다.

 

하여 PriorityQueue 라는 녀석을 사용하였다. 이 녀석은 add 해준 후에 poll() 또는 peek() 메소드를 실행하면 알아서 가장 낮은 순위의 값을 리턴해준다. 물론 처음 선언시 

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

와 같은 형태로 선언해주면 가장 높은 값을 리턴해준다.

 

[알고리즘 Flow]

1. PriorityQueue에 주어진 음식지수의 배열 값을 넣어준다.

2. PriorityQueue의 길이가 1보다 클때까지 while문을 반복할 것이다.
   (숫자가 2개필요하기때문에 1보다 작을때도 while문이 동작하면 NPE HELL 이다.

3. PriorityQueue에서 숫자 두개를 꺼내서 스코빌계산식에 맞게 계산한 값을 다시 PriorityQueue에 add해준다.
   (그러면서 섞은 횟수 즉, answer를 1씩 추가해준다.)

4. 그러다가 만약 PriorityQueue의 맨앞의 숫자가 목표 스코빌지수와 같거나 높다면 반복문을 중단한다.

5. 근데 여기서 PriorityQueue의 맨 앞의 숫자가 목표 스코빌지수보다 낮다면 -1을 리턴해준다.
   (계산을 했는데도 낮다는 건 목표 스코빌지수를 달성 할 수 없는 숫자들로 이루어졌기 때문)
6. 그게 아니라면 answer 리턴

 

[나의 코드]

import java.util.Arrays;
import java.util.PriorityQueue;

public class scoville {

	public static void main(String[] args) {
		
		int [] scoville = {0, 0, 0, 0};		
		int k = 7;

		solution(scoville, k);
	}
	
	public static int solution(int[] scoville, int k) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i = 0; i < scoville.length; i++) {
			pq.add(scoville[i]);
		}
        
        while(pq.size() > 1) {
        // 큐의 사이즈가 1보다 클때까지 반복한다.
        System.out.println(pq);
        	if (pq.peek() < k) {
        	// 현재 가장 작은 큐의 숫자가 기준 스코빌 지수보다 작다면 2개를 뽑아서 스코빌계산식으로 더해준 다음, 다시 큐에 넣어준다.
        		int temp1 = pq.poll();
            	int temp2 = pq.poll();
            	System.out.println(temp1 + " : " + temp2);
            	System.out.println(getScoville(temp1, temp2));
            	pq.add(getScoville(temp1, temp2));
            	answer++;
        	} else {
        		break;
        	}
	
        }
        
        System.out.println(pq);
        
        if (pq.peek() <= k) {
        	answer = -1;
        }
        
        System.out.println(answer);
        return answer;
    }
	
	private static int getScoville(int a, int b) {
		return a + (b * 2);	
	}
	
}

---

[깃허브]

https://github.com/RUCKUSJERRY/practiceOfJava/blob/main/Prs_Pratice/src/com/level02/scoville.java

RUCKUSJERRY/practiceOfJava