프로그래머스_42626_더 맵게

목차

👆 링크
🤞 문제
👌 코드
🖖 풀이
🖐 Git gist 주소

📌 링크

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

📝 문제

  매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어한다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해서는 다음과 같은 규칙에 따라야 한다.

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

💻 코드

package programmers_42626_moreSpicy;

import java.util.*;

/*
 * 
 * 프로그래머스
 * 42626. 더 맵게
 * https://programmers.co.kr/learn/courses/30/lessons/42626
 * 2021-05-17
 * 
 * */
public class Solution2 {
	static PriorityQueue<Integer> scovilles = new PriorityQueue<>();
	
	public int solution(int[] scoville, int K) {
		int answer = 0;
		
		//1. q에 scoville 옮겨담는다.
		initScoville(scoville);
		
		int scale1, scale2;
		while(!scovilles.isEmpty()) {
			if(scovilles.peek() >= K) break;
			if(scovilles.size() <= 1) return -1; //모든 음식의 지수를 K이상으로 만들수 없는 경우에는 -1 리턴
			
			answer++;
			scale1 = scovilles.poll();
			scale2 = scovilles.poll();
			scovilles.add(scale1 + scale2 * 2);
		}
		
		
		return answer;
	}

	
	private void initScoville(int[] scoville) {
		for(int s : scoville) {
			scovilles.add(s);
		}
	}
}

✍ 풀이

👉 오름차순으로 정렬 후, 스코빌 지수가 가장 작은 음식과 두 번째로 작은 음식을 꺼낸다.
👉 규칙대로 섞은 후 다시 배열에 넣는 것을 반복한다.

1. 스코빌 지수를 담는 객체는 어떤 타입으로 선언해야 하는가?

❌ 배열, 리스트
데이터의 추가와 삭제가 빈번하게 일어나기 때문에 적합하지 않다.

⭕ Stack, Queue
때문에 Stack과 Queue가 이번 문제에 적합하다.

2. Stack 으로 접근할 경우

처음 스코빌 지수를 Stack에 담아 풀었을 때, 아래의 순서를 반복했다.

(1) 주어진 스코빌 지수를 Stack에 넣는다.
(2) 정렬한다.
(3) 스코빌 지수가 가장 작은 음식과 두번째로 작은 음식을 꺼내 섞고, 다시 Stack에 담는다.
(4) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 (2)와 (3)을 반복한다.

package programmers_42626_moreSpicy;
import java.util.*;
/*
 * 
 * 프로그래머스
 * 42626. 더 맵게
 * https://programmers.co.kr/learn/courses/30/lessons/42626
 * 2021-05-14
 * 
 * */
class Solution {
	static int answer = 0;
	static int wants;
	static Stack<Integer> stack = new Stack<>();
	
    	public int solution(int[] scoville, int K) {
    	
		initData(scoville, K);

		/*
		 * 	scoville				K	return
				[1, 2, 3, 9, 10, 12]	7	2
		 * */


		if(stack.peek() < K) {
			answer = blend();
		}

		return answer;
    	}

	private void initData(int[] scoville, int K) {
		for(int i = 0; i < scoville.length; i++) {
			stack.push(scoville[i]);
		}
		wants = K;
		
		//내림차순 정렬
		Collections.sort(stack, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
        	});
	}

	private int blend() {
		if(stack.isEmpty()) return -1;
		
		answer++;
		
		//섞기
		int after = stack.pop() + stack.pop() * 2;
		stack.push(after);
		
		//내림차순정렬
		Collections.sort(stack, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
        	});
		
		if(stack.peek() < wants) {
        	blend();
        	}
		
		return answer;
	}
}

바로 시간복잡도 때문이다.


만약 N개의 스코빌 지수가 주어진다고 가정하면,

(1) O(N) + (2) O(NlogN) + (3) O(1) + (4) O(NlogN) * O(N)

즉, 최소 O(NlogN) * O(N)의 시간복잡도가 소요된다.

만약 scoville 길이가 최대값인 100만인 경우에는 시간복잡도가 1억 * 100만 = 100조가 되어 터져버리게 되는 것이다.

그러면 도대체 어떻게 풀어야 하는 것일까?

3. PriorityQueue 로 접근할 경우

  먼저 우선순위 큐(PriorityQueue)란, 먼저 들어온 데이터가 먼저 나가는 구조(FIFO) 를 따르지 않고, 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조이다.

 또한, 삽입 시 logN의 시간복잡도가 걸린다. 즉, NlogN이 아닌 logN의 시간복잡도로 정렬이 가능해지며, 매우 쉽게 시간 초과가 나는 문제를 해결할 수 있다.

👩‍💻 Git gist 주소

https://gist.github.com/ysyS2ysy/3b471c501466d2bca3c54d6535dcba26