알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서
그 어떤 문제에 대한 비판 지적 방향제시는 언제나 감사하게 받겠습니다.
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어
수신 탑(높이)
I 숫자
큐에 주어진 숫자를 삽입합니다.
D 1
큐에서 최댓값을 삭제합니다.
D -1
큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
operations
return
[I 16,D 1]
[0,0]
[I 7,I 5,I -5,D -1]
[7,5]
입출력 예 설명
16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다. 7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.
해결 방법
생각한 해결방법은 두가지 이다. 하나는 문제의 제목처럼 우선순위큐를 두개를 선언하여 이중으로 해결하는 것 과, ArrayList 를 Deque 자료구조 처럼 사용하여 문제를 해결하는 방식이다.
전자는 PriorityQueue<Integer> 와 PriorityQueue<Data> 를 사용하여 풀 수 있다.
static class Data implements Comparable<Data>{
int number;
Data(int number){
this.number = number;
}
@Override
public int compareTo (Data target){
return this.number <= target.number ? 1 : -1;
}
}
위와 같이 Data 클래스를 구현해 주어 하나는 오름차순, 하나는 내림차순으로 구현하여 문제를 해결할 수 있다.
이번 문제 제출은 전자의 방법보다 후자의 방법을 통하여 문제를 제출하였다. 하나의 ArrayList 를 선언해 주었고, operations 의 String 을 split(" ") 으로 분열하여 String[] temp 에 저장하였다. 후에 temp[0].equals("I") or temp[0].equals("D") 의 경우로 나눠 offer 와 poll 연산을 진행하였다.
poll 연산의 경우 우선적으로 !ArrayList.isEmpty() 인 경우로 검사를 먼저 하였고, temp[1] 이 "1" 이 '맞는' 경우 GetMaxIndex 함수를 사용하여 ArrayList.remove(GetMaxIndex); temp[1] 이 "1" 이 '아닌' 경우 GetMinIndex 함수를 사용하여 ArrayList.remove(GetMinIndex); 를 통하여 poll 연산을 진행하였다.
이런식으로 한 이유는 계속된 정렬을 사용하기 보다는 O(N) 의 시간으로 제거할 대상을 찾아내는것이 시간 효율이 좋다고 생각해서 사용하였다. Collections.sort 를 사용하여 상시 정렬을 사용하였을 경우, MergeSort 를 사용하여 정렬을 하지만, 문제의 operations 배열의 길이는 1 ~ 1000000 의 길이로, 최악의 경우 n = 1,000,000 일때 n * (n log n) = 1,000,000 * 6,000,000 의 시간복잡도를 갖게된다. 따라서 정렬은 마지막 출력때 한번 실행하여 시간복잡도의 효율을 높였다.
Solution.Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class Programmers_Heap_4 {
public int[] solution(String[] operations) {
int[] answer = {0, 0};
String[] temp;
Queue<String[]> operationQueue = SetQueue(operations);
ArrayList<Integer> dataArrayList = new ArrayList<>();
for(;!operationQueue.isEmpty();){
temp = operationQueue.poll();
if(temp[0].equals("I")){
dataArrayList.add(Integer.parseInt(temp[1]));
}
else if(!dataArrayList.isEmpty()){
if(temp[1].equals("1")){
dataArrayList.remove(GetMaxIndex(dataArrayList));
}
else{
dataArrayList.remove(GetMinIndex(dataArrayList));
}
}
}
Collections.sort(dataArrayList);
if(!dataArrayList.isEmpty()){
answer[0] = dataArrayList.get(dataArrayList.size() - 1);
answer[1] = dataArrayList.get(0);
}
return answer;
}
public Queue<String[]> SetQueue (String[] operations){
Queue<String[]> operationQueue = new LinkedList<>();
for(String operation : operations){
operationQueue.offer(operation.split(" "));
}
return operationQueue;
}
public int GetMaxIndex (ArrayList<Integer> dataArrayList){
int max = dataArrayList.get(0);
int maxIndex = 0;
for(int index = 1, size = dataArrayList.size() ; index < size ; index++){
if(max < dataArrayList.get(index)){
max = dataArrayList.get(index);
maxIndex = index;
}
}
return maxIndex;
}
public int GetMinIndex (ArrayList<Integer> dataArrayList){
int min = dataArrayList.get(0);
int minIndex = 0;
for(int index = 1, size = dataArrayList.size() ; index < size ; index++){
if(min > dataArrayList.get(index)){
min = dataArrayList.get(index);
minIndex = index;
}
}
return minIndex;
}
}
