문제 해석
우선 문제를 보고 든 풀이 흐름은 다음과 같다.
•
1. 정렬이 되야한다.
•
2. 0번째 값이 k보다 커져야 한다.
◦
3-1. 작은 경우, 0,1 번째 음식을 빼낸다.
◦
3-2 두개를 섞는다. newFood = arr[0] + (arr[1]*2)
◦
3-3 섞은 횟수가 1 증가한다 mixCnt++;
◦
3-3. newFood 는 다시 음식 배열에 들어간다
•
4. 다섞어서 음식이 하나남았는데도 K보다 작다면 -1을 반환한다.
여기서 간단히 ArrayList로 풀 수 있지 않을까? 해서 아래 처럼 접근했다.
public class Solution1 {
public int Solution1 (int[] scovilleArr, int targetK){
int answer = 0;
int mixCnt = 0;
ArrayList<Integer> foods = new ArrayList<>();
for(int i=0;i< scovilleArr.length;i++) {
foods.add(scovilleArr[i]);
foods.sort(Comparator.naturalOrder());
}
while (foods.get(0) < targetK) {
if (foods.size() < 2) {
return -1;
}
int newFood = foods.get(0) + (foods.get(1) * 2);
mixCnt++;
foods.remove(0); // 첫 번째 음식 제거
foods.remove(0); // 두 번째 음식 제거
foods.add(newFood); // 새로운 음식 추가
foods.sort(Comparator.naturalOrder());
}
answer = mixCnt;
return answer;
}
public static void main(String[] args){
Solution1 sol = new Solution1();
int[] scoville = {1,2,3,9,10,12};
int k = 7;
System.out.println(sol.Solution1(scoville, k));
}
}
Java
복사
•
문제는 내가 원하는 방식대로 풀이되는 줄 알았지만 문제가 발생했다.
•
나는 가장 작은값, 그 다음값을 찾아내기 위해서 반복문 1회마다 계속해서 정렬하는 방식을 사용하고 있다. 여기서 효율성에 대한 문제가 발생하고 있었다.
•
질답 게시판 들에서도 나와 비슷한 사례가 있었으며 답변에서 매번 정렬을 진행하는것은 성능적 이슈가 있을 것이라는 답변을 보고 다른 방법으로 접근해됨을 알게되었다.
•
중요한것은 최소값을 추출하는 가장 효율적인 방법이 필요했다. 만약 정렬되지 않는다면, 또 비교 검색을 통해서 가장 작은값을 추출해야 할텐데 비효율적일 것이다.
•
여기서 ChatGPT의 도움을 통해 어떤 방식이 최소값을 추출하는데 가장 적합할지 찾아보니 다음과 같은 답변을 얻을 수 있었다.
매번 정렬하는 부분이 효율성에 영향을 미치고 있다면, 정렬을 최소화하는 방법을 찾아보는 것이 좋아. ArrayList에서 가장 작은 값과 그 다음 값을 찾는 방법을 바꿔보자.
대신에 PriorityQueue를 사용하면 효율적으로 최소값을 추출할 수 있어. PriorityQueue는 내부에서 힙(heap)을 사용하여 최소값을 빠르게 추출할 수 있도록 도와줘.
여기서 PriorityQueue 를 통해서 구현하는 것이 올바른 접근 방법임을 알게되었다. 하지만 해당 자료구조를 처음 본 상황이라 예제들을 찾아봐야 했다. 이것은 우선순위 큐라고 불리우는 자료구조였다.
문제 풀이
우선순위 큐를 선언하고 단순히 배열에 넣었을 뿐인데 peek을 통해 조회하면 자동으로 최소값을 찾아주었다. 또한 추출하는 poll도 마찬가지로 최소값이 추출되고, 그 다음 요소는 다시 최소값이되어 poll을 통해 최초의 최소값, 그다음 최소값으로 newFood 연산을 할 수 있었고 이걸 다시 add로 큐에 넣으면 자동으로 정렬되는 방식이다.
지금은 최소값으로 정렬되고 있는것이 기본값(Default)기 때문이며, 정렬 방식을 최대값으로 조절한다면 다른 문제들도 이처럼 응용하여 풀 수 있을 것으로 보여진다. 이 자료구조는 정말 유용하게 사용 될 것으로 생각되었다.
import java.util.PriorityQueue;
public class Solution2 {
public int Solution2(int[] scovilleArr, int targetK) {
int answer = 0;
int mixCnt = 0;
// 우선순위 큐 선언
PriorityQueue<Integer> foods = new PriorityQueue<>();
// 우선순위 큐에 배열 넣기
for (int scoville : scovilleArr) {
foods.add(scoville);
}
while (foods.peek() < targetK) {
if (foods.size() < 2) {
// 음식이 하나만 남았는데도 K 이상이 되지 않으면 -1 반환
return -1;
}
int newFood = foods.poll() + (foods.poll() * 2);
mixCnt++;
foods.add(newFood);
}
answer = mixCnt;
return answer;
}
public static void main(String[] args) {
Solution2 sol = new Solution2();
int[] scoville = {1, 2, 3, 9, 10, 12};
int k = 7;
System.out.println(sol.Solution2(scoville, k));
}
}
Java
복사
최대값으로 정렬하도록 우선순위 큐를 선언하는 방법
위에서 설명한것과 같이 기본적으로 최소값부터 오름차순이 기본 설정이다. 경우에 따라 최대값부터 내림차순이 필요 할 수도 있다.
PriorityQueue는 디폴트로 작은 값부터 큰 값 순서로 정렬되는 최소 힙(Min Heap)입니다. 그래서 poll() 메서드를 호출할 때마다 가장 작은 값을 반환하게 됩니다.
만약 큰 값부터 작은 값 순서로 정렬하고 싶다면, PriorityQueue를 초기화할 때 Comparator를 지정해주면 됩니다. 아래는 큰 값부터 작은 값 순서로 정렬되도록 Comparator를 지정하는 예제입니다.
이렇게 하면 최대 힙(Max Heap)으로 동작하게 되어 큰 값이 먼저 나오게 됩니다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
// 또는
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
Java
복사