99클럽 코테 스터디 9일차 TIL 더 맵게

📝 문제

프로그래머스

🔥 시도해본 접근 방식

이번 문제를 보았을 때 힙을 사용하여 푸는 문제였기 때문에

힙 자료구조에 대한 개념이 부족하여 다음 포스팅을 참고하여 개념에 대해 알아보았다.

[알고리즘 - 힙 정렬(Heap Sort)

힙 정렬을 알아보기 전에 이진트리에 대해서 알아야한다.이진트리(Binary Tree)는 컴퓨터가 데이터를 표현할때, 데이터를 두개씩 이어붙이는 것을 말한다.각 데이터는 노드라고 말한다.가장 최상

알고리즘 - 힙 정렬(Heap Sort)

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        List<Integer> scovilleList = new ArrayList<>();

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

        int answer = 0;

        PriorityQueue<Integer> pq;

        do {
            pq = new PriorityQueue<>(scovilleList);

            if (pq.peek() < K) {
                answer++;

                int mixedScoville = pq.poll() + pq.poll() * 2;

                scovilleList = scovilleList.subList(2, scovilleList.size());
                scovilleList.add(0, mixedScoville);
            }

        } while (scovilleList.size() >= 2 && pq.peek() < K);

        return answer == 0 ? -1 : answer;
    }
}

위 코드와 같이 작성하여 첫번째 제출을 하였는데 실패하였고 이유를 찾지 못해 프로그래머스 AI 피드백이라는 기능을 통해서 잘못된 부분을 찾았다.

우선 PriorityQueue를 사용하면 반복문에서 매번 다시 선언하지 않아도 값이 제거되고 추가됨에 따라 자동적으로 정렬되기때문에 불필요한 코드가 있었다.

또 하나는 만약 입력으로 받은 배열의 가장 맵지 않은 음식이 처음부터 K보다 클때 0이아닌 -1로 리턴되고 있다는 점 이었다.

이부분을 개선하여 다음 답안을 제출하였다.

2️⃣ 두번째 시도

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        List<Integer> scovilleList = new ArrayList<>();

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

        int answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(scovilleList);

        if (pq.peek() > K) {
            return 0;
        }

        while (pq.size() >= 2 && pq.peek() < K) {
            int mixedScoville = pq.poll() + pq.poll() * 2;

            pq.offer(mixedScoville);

            answer++;
        }

        return answer == 0 ? -1 : answer;
    }
}

위 코드와 같이 수정 후 제출하였지만 또 다시 실패하였는데 이번에도 원인을 찾지 못하여 AI 피드백의 도움을 받았다.

실패했던 원인은 만약 반복문을 마친 후에 K 보다 매운 음식을 만들 수 없을 떄에는 -1을 리턴해야 하는데 이미 answer가 0이 아니기 때문에 반복 횟수를 리턴하고 있었던 결함이 있었다.

✨ 성공 코드

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        List<Integer> scovilleList = new ArrayList<>();

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

        // 가장 맵지 않은 순서대로 정렬된 최소 힙을 만들기위해 위해 우선순위 큐 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>(scovilleList);

        // 만약 가장 맵지 않은 음식이 K 보다 크다면 0을 리턴
        if (pq.peek() > K) {
            return 0;
        }

        int answer = 0;

        while (pq.size() >= 2 && pq.peek() < K) {
            int mixedScoville = pq.poll() + pq.poll() * 2;

            pq.offer(mixedScoville);

            answer++;
        }

        // 만약 K보다 매운 음식을 만들 수 없다면 -1 리턴
        if (pq.peek() < K) {
            return -1;
        }

        return answer;
    }
}

위와 같이 수정하여 최종적으로 풀이에 성공하였다.