더 맵게 (with.Java)

“더 맵게 (with.Java)” 문제에 대하여 알아본 글입니다.

코딩 테스트 문제를 풀며, 풀었던 문제에 대한 회고와 다른 풀이 방법을 알아보며, 알아가고자 합니다.

문제에 대해 먼저 알아보겠습니다.

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예시

문제에 대한 나의 풀이

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> que = new PriorityQueue<>();
        for(int i : scoville){
            que.add(i);
        }

        int answer = 0;
        while(que.peek() < K){
            que.add(que.poll() + (que.poll() * 2));
            answer++;
            if(que.size() == 1 && que.peek() < K){
                return -1;
            }
        }

        return answer;
    }
}

풀이 리뷰

solution 메서드는 두 개의 배열 progresses와 speeds를 입력으로 받습니다.

작업의 진행 상황과 속도를 이용하여 각 작업이 완료되는 데 필요한 일 수를 계산합니다.

Queue 객체 que를 생성하여 각 작업의 완료까지 걸리는 일 수를 저장합니다.

첫 번째 for 루프를 통해 각 작업에 대해 필요한 일 수를 계산하고, 이를 que에 저장합니다. 만약 속도에 따라 작업 완료까지 걸리는 일 수가 소수점으로 나누어 떨어지지 않으면 올림하여 계산합니다.

compare 변수에 첫 번째 작업의 필요한 일 수를 저장하고, count 변수를 초기화합니다.

두 번째 while 루프를 통해 que가 빌 때까지 반복하며 각 작업의 완료까지 걸리는 일 수를 비교하여 처리합니다.

compare와 현재 작업의 필요한 일 수를 비교하여 작거나 같으면 작업을 완료했으므로 count를 증가시키고 que에서 작업을 제거합니다.

그렇지 않으면 새로운 작업이 시작되었으므로 list에 현재까지 완료된 작업의 수를 추가하고 count를 초기화합니다. 또한 compare를 업데이트합니다.

마지막으로 list에 저장된 값을 배열로 변환하여 반환합니다.

이 코드는 각 작업이 완료되는 데 필요한 일 수를 계산하고, 각 날짜별로 완료되는 기능의 수를 계산하여 반환하는 문제를 해결합니다.

배열로도 풀어보겠습니다.

문제에 대한 나의 풀이

import java.util.ArrayList;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {

        ArrayList<Integer> list = new ArrayList<>();
        int day = 0;
        int count = 1;
        int idx = 0;
        for(int i = 0; i < progresses.length; i++){
            if(day * speeds[i] + progresses[i] >= 100){
                count++;
            }else if(i != 0){
                list.add(count);
                count = 1;
            }
            int temp = 100 - progresses[i];
            if(temp % speeds[i] == 0){
                int temp2 = temp / speeds[i];
                if(day < temp2){
                    day = temp2;
                }
            }else{
                int temp2 = temp / speeds[i] + 1;
                if(day < temp2){
                    day = temp2;
                }
            }
        }
        if(day * speeds[progresses.length - 1] + progresses[progresses.length - 1] >= 100){
            list.add(count);
        }



        int[] answer = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            answer[i] = list.get(i);
        }

        return answer;
    }
}

풀이 리뷰

solution 메서드는 정수 배열 scoville과 정수 K를 입력으로 받습니다.

우선순위 큐 PriorityQueue를 생성합니다.

scoville 배열의 각 요소를 우선순위 큐에 삽입합니다.

answer 변수를 초기화하고, 스코빌 지수가 K 이상이 될 때까지 반복합니다.

반복문 내에서는 현재 우선순위 큐의 맨 앞 요소가 K보다 작다면, 가장 작은 두 개의 값을 꺼내서 섞은 후 다시 큐에 삽입합니다. 이때 섞은 결과는 첫 번째 값 + (두 번째 값 * 2)로 계산됩니다.

섞은 횟수를 answer에 1 증가시킵니다.

반복문이 종료될 때까지 스코빌 지수가 K 이상이 되지 않았다면 -1을 반환합니다.

그렇지 않으면 answer를 반환합니다.

이 코드는 주어진 조건에 따라 음식을 섞어야 하는 최소 횟수를 계산하는 문제를 해결합니다.