[Algorithm] 프로그래머스 - 더 맵게 (Java)

[문제]

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

코딩테스트 연습 - 더 맵게

[풀이]

모든 원소가 매개변수 K보다 커질때까지 배열의 원소 중 가장 작은 수, 2번째로 작은 수 => 가장 작은 수 + (2번째로 작은 수*2)로 바꾸면서 바꾼 횟수를 리턴하는 문제로 크게 3가지의 경우로 나눠 문제를 풀었지만... 정답은 아니었다.

 

일단 배열을 정렬한 후에 다음과 같은 함수 작성

1. 가장 작은 수가 k보다 작고 배열 길이가 2 이상인가?

• 가장 작은 수 + (2번째로 작은 수*2)로 바꾸고 횟수를 나타내는 count +1, 그리고 함수 호출

2. 배열 길이가 1이고 값이 k보다 작은가 ? 

• 그럴 경우 더이상 수를 합칠 수 없으므로 -1을 반환

3. 위의 2가지 경우가 아닌 경우 (모든 원소의 값이 k이상인 경우)

• 그동안 숫자를 합친 횟수 count 반환 

[내가 작성한 코드]

import java.util.*;

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

        for(int num : scoville){
            list.add(num);
        }

        return function(list,K);
    }

    public static int function(List<Integer> list, int K){
        Collections.sort(list);
        if(list.get(0) < K && list.size() >= 2){
            int smallest = list.remove(0);
            int smaller = list.remove(1);

            list.add(smallest + smaller*2);
            ++count;
            function(list,K);
        }else if(list.get(0) < K && list.size() < 2){
            count = -1;
        }else if(list.get(0) >= K){
            return count;
        }
        return count;
    }
}

 

문제는 heap을 이용해야 하기에 우선순위 큐(PriorityQueue)를 이용해서 다시 풀었다.

참고로 우선순위 큐는 일반적인 Queue 구조에서 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트부터 먼저 나가는 자료구조이다.

 

우선순위 큐 특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야 함)
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음
• 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)
• 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임

PriorityQueue 선언

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

PriorityQueue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

add(value), offer(value) 두가지 모두 값을 추가하고 삽입 성공/실패 여부(boolean)를 반환하지만 add이 경우 성공하면 true, 저장공간이 부족하면 IllegalStateException이 발생한다.

 

PriorityQueue 값 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거, 비어 있으면 NoSuchElementException 발생
priorityQueue.clear();      // priorityQueue에 초기화

 

Priority Queue에서 우선순위가 가장 높은 값 출력

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();//int형 priorityQueue 선언
priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1 (삭제없이 요소를 읽어온다)

 

[향상된 코드]

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int answer = 0;
        for(int num : scoville){
            queue.offer(num);
        }

        while(queue.peek() < K){
            if(queue.size() < 2){
                return -1;
            }

            int f1 = queue.poll();
            int f2 = queue.poll();

            int newFood = f1 + (f2*2);
            queue.offer(newFood);
            answer++;
        }
        return answer;
    }
}