출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다
문제
문제 분석
가장 작은것 2개를 빼내서 곱하고 합한 다음 다시 비교하는 문제입니다. 조건을 만족할 때까지 항상 가장 작은것 2개를 빼내는것이 핵심입니다.
풀이
나의 풀이
import java.util.*;
import java.util.stream.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
List<Integer> list = Arrays.stream(scoville).boxed().collect(Collectors.toCollection(ArrayList::new));
while(list.size() > 2){
Collections.sort(list);
if(list.get(0) >= K) break;
int first = list.remove(0);
int second = list.remove(0);
int mix = first + (second * 2);
list.add(0,mix);
answer++;
}
if(list.get(0) < K) return -1;
return answer;
}
}가장 작은 2개를 골라서 곱하고 합한다음 다시 넣고 정렬하는 것을 반복하였습니다. 2개를 꺼내야 하므로 리스트의 요소가 2개 이상일때 까지만 계산하거나 최소가 K이상일때까지 계산하였습니다.
강의의 풀이
단순히 리스트를 이용
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
List<Integer> list = new LinkedList<>();
for(int s : scoville) list.add(s);
Collections.sort(list);
int answer = 0;
while(list.size() >= 2 && list.get(0) < K){
int s1 = list.remove(0);
int s2 = list.remove(0);
int s3 = s1 + s2 * 2;
list.add(s3);
answer++;
Collections.sort(list);
}
if(list.get(0) < K) return -1;
return answer;
}
}리스트를 이용한 풀이는 저와 같이 2개 이상이거나 최소가 K이하일때 까지 가장 작은 요소 2개를 빼서 곱하고 합한다음 넣고 정렬하는 과정을 반복하였습니다.
하지만 효율성에서 문제가 발생하였습니다.
Collections.sort(리스트)를 통해 매 연산마다 리스트를 정렬해 주어야 하기 때문에 큰 낭비가 발생합니다.
Min Heap
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
Queue<Integer> list = new PriorityQueue<>();
for(int s : scoville) list.add(s);
int answer = 0;
while(list.size() >= 2 && list.peek() < K){
int s1 = list.poll();
int s2 = list.poll();
int s3 = s1 + s2 * 2;
list.offer(s3);
answer++;
}
if(list.peek() < K) return -1;
return answer;
}
}Min Heap을 이용하면 따로 정렬하지 않아도 항상 정렬 상태를 유지할 수 있습니다.
자바에서 Heap은
PriorityQueue를 통해 손쉽게 사용할 수 있습니다.
LinkedList<>()를 대신해 PriorityQueue<>()를 사용하였고 정렬을 하는 연산이 필요가 없습니다.
GitHub
오늘도 내일도 화이팅!