[Algorithm] 프로그래머스 Lv2 더 맵게

안녕하세요 rosepurple입니다. :)

오늘 푼 알고리즘 문제 풀이를 작성해보도록 하겠습니다!

문제

오늘은 아래 문제를 풀어봤습니다. (약 50분 소요)

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

코딩테스트 연습 - 더 맵게

풀이

처음에는 익숙한 ArrayList로 풀려고 시도해봤는데 루프 문을 돌 때마다 정렬을 해주다 보니까 효율성에서 초과가 났습니다..!

그래서 질문하기 게시판을 참고해서 우선순위 큐로 풀었는데요!

 

int answer = 0;
PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();

Integer형 우선순위 큐를 값이 낮은 것부터 우선순위가 높게 설정했습니다.

(값이 높은 것부터 우선순위가 높게 설정하려면 new PriorityQueue<>(Collections.reverseOrder())로 설정해주면 됩니다.)

 

for (int s: scoville) {
    scovilleQueue.add(s);
}

그 후에 매개변수로 들어오는 스코빌 지수 배열을 우선순위 큐에 추가해줍니다.

 

while (scovilleQueue.peek() < K) {
    if (scovilleQueue.size() == 1 && scovilleQueue.peek() < K) {
        answer = -1;
        break;
    }
    ...
}

우선 while문을 순회할건데 가장 처음의 값이 맞추려는 스코빌 지수 K보다 낮을 경우에만 순회합니다.

만약 모든 음식을 조합했는데도 K보다 낮으면 answer을 -1로 초기화하고 while문을 탈출합니다.

( PriorityQueue.peek() : 가장 높은 우선순위의 값을 제거 없이 조회 )

 

int first = scovilleQueue.poll();
int second = scovilleQueue.poll();
scovilleQueue.add(first + (second * 2));

그다음에는 스코빌 지수가 가장 낮은 것과 두 번째로 낮은 것을 조합해줍니다.

( PriorityQueue.poll() : 가장 높은 우선순위 값을 제거하며 반환 )

 

answer++;

while문이 끝나기 전에 반복 횟수인 answer을 하나 더해주고 while문 처음으로 순회합니다.

전체 코드

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> scovilleQueue = new PriorityQueue<>();

        for (int s: scoville) {
            scovilleQueue.add(s);
        }

        while (scovilleQueue.peek() < K) {
            if (scovilleQueue.size() == 1 && scovilleQueue.peek() < K) {
                answer = -1;
                break;
            }

            int first = scovilleQueue.poll();
            int second = scovilleQueue.poll();
            scovilleQueue.add(first + (second * 2));

            answer++;
        }

        return answer;
    }
}

마무리

만약 궁금한 점이 있으시다면 편하게 댓글 남겨주세요!

이번 포스팅도 읽어주셔서 감사합니다. :)