[JAVA] Programmers <Heap LV3> 이중 우선순위 큐

명령어 데이터를 받아서 이를 따로 읽어들여 연산을 처리하는 이중 Priority Queue를 구성하면 되는 문제인 것 같다.

이런 LV3 문제들은 제한 사항을 똑바로 숙지하지 않아서 삽질을 하는 경우가 꽤 있었으므로, 제한 사항을 따로 적어 확실하게 하고 넘어가는 것이 좋겠다는 생각이 든다...ㅎㅎ 어제 데어봐서..

 

제한 사항: 

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

---

첫 시도는 오름차순과 내림차순으로 정렬하는 Priority Queue를 2개 생성하여 명령이 들어오면 최댓값 or 최솟값 여부를 판단하여  최댓값을 삭제하는 연산이면 maxQue를, 최솟값을 삭제하는 연산이면 minQue의 peek을 삭제하는 식으로 진행했다. 

모든 명령어에 대한 연산이 끝난 뒤에는 각 큐에 남아있는 숫자를 서로 비교하여 두 Queue가 공통적으로 가지고 있는 수만 따로 받아, 받은 수의 집합에서 각각 최대, 최소 값을 구하는 식으로 코드를 작성했고, 당연히 될 것이라고 확신했다...

---

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
	public Queue<Integer> minQue = new PriorityQueue<>();
	public Queue<Integer> maxQue = new PriorityQueue<>(1000002, Collections.reverseOrder());

	public int[] solution(String[] operations) {
		int[] answer = new int[2];
		List<Integer> commonList = new ArrayList<>();

		for (int i = 0; i < operations.length; i++) {
			command(operations[i]);
		}

		while (true) {
			int i = 0;
			if (i < minQue.size()) {
				int temp = minQue.poll();
				if (maxQue.contains(temp)) {
					commonList.add(temp);
				}
			} else break;
		}
		
		if(commonList.isEmpty()) {
			answer[0] = 0;
			answer[1] = 0;
		} else {
			answer[0] = commonList.get(commonList.size()-1);
			answer[1] = commonList.get(0);
		}
		return answer;
	}

	public void command(String command) {

		String[] com = command.split(" ");

		if (com[0].equals("I")) {
			minQue.add(Integer.parseInt(com[1]));
			maxQue.add(Integer.parseInt(com[1]));
		} else if (com[0].equals("D")) {
			if (com[1].equals("-1")) {
				if (!minQue.isEmpty()&&maxQue.contains(minQue.peek())) minQue.poll();
			} else if (com[1].equals("1")) {
				if (!maxQue.isEmpty()&&minQue.contains(maxQue.peek())) maxQue.poll();
			}
		}
	}
}

깊게 생각 안 했을 때는 "...? 맞는 코드 아닌가?" 싶긴 했다.

그러나 예제를 돌려보니

이와 같이 Queue가 완전히 비었다가 다시 채워지는 과정이 빈번한 케이스에서 현재 Queue가 비어있는지 판단을 잘 못하고 삭제 연산 한 번이 누락되었다. (최소한 어떤 과정이 문제인지 이해는 하겠으니 최악은 아니다.)

노트를 꺼내고 다시 한번 생각을 해보자.

 

---

아무래도, 두 Queue 간에 공통 인자가 없는지 여부를 판단하는 연산이 모든 명령어 입력이 끝난 뒤 한 번만 이뤄지니, 현재 Queue가 비어있는지 여부가 확인이 제대로 이뤄지지 않는 것 같다.

그래서 명령어 받을 때마다, 두 Queue에 공통 인자가 있는지 판단하고, 공통 인자가 없다는 것은 현재 Queue에 아무 값도 없다는 것이니, minQue와 maxQue를 모두 clear 하는 과정을 command 메서드에 추가했다.

 

---

package com.choonham;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
	public Queue<Integer> minQue = new PriorityQueue<>();
	public Queue<Integer> maxQue = new PriorityQueue<>(1000002, Collections.reverseOrder());

	public int[] solution(String[] operations) {
		int[] answer = new int[2];
		List<Integer> commonList = new ArrayList<>();

		for (int i = 0; i < operations.length; i++) {
			command(operations[i]);
		}

		while (true) {
			int i = 0;
			if (i < minQue.size()) {
				int temp = minQue.poll();
				if (maxQue.contains(temp)) {
					commonList.add(temp);
				}
			} else break;
		}
		
		if(commonList.isEmpty()) {
			answer[0] = 0;
			answer[1] = 0;
		} else {
			answer[0] = commonList.get(commonList.size()-1);
			answer[1] = commonList.get(0);
		}
		return answer;
	}

	public void command(String command) {
		
		String[] com = command.split(" ");

		if (com[0].equals("I")) {
			minQue.add(Integer.parseInt(com[1]));
			maxQue.add(Integer.parseInt(com[1]));
		} else if (com[0].equals("D")) {
			if (com[1].equals("-1")) {
				if (!minQue.isEmpty()) minQue.poll();
			} else if (com[1].equals("1")) {
				if (!maxQue.isEmpty()) maxQue.poll();
			}
		}
		if(!maxQue.contains(minQue.peek())) {
			minQue.clear();
			maxQue.clear();
		}
	}
}

이러면 언급한 문제점이 사라지니, 모든 케이스에서 정답을 도출할 수 있다.

 

사실, 제출하고 "이게 되네;;"라는 생각이 들었다. 

단 1개의 데이터만 Queue에 남아있는 경우를 아예 생각 안 하고 풀었는데 정답으로 인식이 되는 걸 보면, 그런 케이스는 없나 보다. 

 

딱히 신경 안 써도 되는 걸 실제로 신경 쓰지 않았다. <- 실력이 늘고 있다는 증거...? ㅋㅋ

 

끝!