2023.08.30.WED

[ 프로그래머스 ]

[ 더 맵게 ]

: 의미없는 숫자인 0을 삭제하는 등 온갖 방법을 사용하고, 정렬도 Collections.sort() 사용 안 하고 버블 정렬로 직접 구현해서, 시간복잡도를 처음에 비해 10배 가까이 줄였는데도 효율성 테스트 통과 못 함 ㅠㅠ

PriorityQueue 이용하는 거 말고는 답이 없는 거냐,,,
우선순위 큐 쓰니까 아주 손쉽게 걍 바로 풀림.

우선순위 큐 작동 원리 : https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

//방법 1 - 효율성 테스트 실패
import java.util.*;
import java.util.stream.*;

class Solution {
    static List<Integer> list;
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        //스코빌 배열 -> 리스트
        list = Arrays.stream(scoville).boxed()
            .collect(Collectors.toList());
        
        list.remove(Integer.valueOf(0));
        sortList(list);
        
        //가장 작은 스코빌 1, 2를 조합하여 새로운 음식 만들기
        while(true){
            if(list.get(0)>=K){
                break;
            }
            
            if(list.size()==1 && list.get(0)<K){
                answer = -1;
                break;
            }
            
            int small1 = list.remove(0);
            int small2 = list.remove(0);
            
            int newOne = getNewScoville(small1, small2);
            list.add(0, newOne);
            sortList(list);
            answer++;
        }
        
        return answer;
    }
    
    public static int getNewScoville(int smaller, int bigger){
        return smaller + (bigger*2);
    }
    
    public static void sortList(List<Integer> list){
        int count = 0;
        
        for(int i=0; i<list.size(); i++){
            for(int j=0; j<list.size()-1-i; j++){
                if(list.get(j)>list.get(j+1)){
                    swap(j, j+1);
                    count++;
                }
            }
            if(count==0) {
                break;
            }
            count = 0;
        }
    }
    
    public static void swap(int x, int y){
        int temp = list.get(x);
        list.set(x, list.get(y));
        list.set(y, temp);
    }
}

//방법 2 - 통과
import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int s : scoville){
            if(s!=0) {
                queue.add(s);
            }
        }
        
        while(true){
            int cur = queue.peek();
            if(cur >= K){
                break;
            }
            
            if(queue.size()==1 && cur < K){
                answer = -1;
                break;
            }
            
            cur = queue.poll();
            int next = queue.poll();
            queue.add(cur + next*2);
            answer++;
        }
        
        return answer;
    }
}

• Deque (양방향 큐)
  https://soft.plusblog.co.kr/24