1. ๋ฌธ์ ์ ๋ํ์ฌ ๐ฆ
(1) ์กฐ๊ฑด ๋ถ์ ๐
์ด์ค ์ฐ์ ์์ ํ๋ ๋ค์ ์ฐ์ฐ์ด ๊ฐ๋ฅํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์๋ฏธํ๋ค.
I ์ซ์: ํํ์ ๋ช ๋ น์ด๋ ํ์ ์ฃผ์ด์ง ์ซ์๋ฅผ ์ฝ์D 1: ํ์์ ์ต๋๊ฐ์ ์ญ์ D -1: ํ์์ ์ต์๊ฐ์ ์ญ์
2. ์ฝ๋๊ฐ ๋์ค๊ธฐ๊น์ง ๐ ๏ธ
KEY WORD: ์ฐ์ ์์ ํ, HashMap maxHeap, minHeap
Java์๋ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ArrayDeque์ฒ๋ผ ๋จธ๋ฆฌ์ ๊ผฌ๋ฆฌ์์ ๋์์ ๋บ ์ ์๋ ์๋ฃ ๊ตฌ์กฐ๊ฐ ์๊ธฐ ๋๋ฌธ์, ์ฐ์ ์์ ํ๋ฅผ ๋ ๊ฐ ํ์ฉํ์ฌ์ผ ํ๋ค.
์ด๋ ๋ง์ ์ฌ๋๋ค์ด ๊ถ๊ธํดํ ๊ฒ์ '์ด๋ป๊ฒ ์ด ๋์ Sync๋ฅผ ๋ง์ถ ๊ฑฐ๋' ๋ ๊ฒ์ผ ๊ฑฐ๋ค.
๋ง์ฝ ์ซ์ ๋ด๋ฆผ์ฐจ์ ํ์์ ๊ฐ์ ํ๋ ๋บ๋๋ฐ, ๊ทธ๊ฒ์ด ์ค๋ฆ์ฐจ์ ํ์์ ์ด๋ฏธ ์ญ์ ๋ ๊ฐ์ด๋ผ๋ฉด, ๊ทธ ๊ฐ์ ๋ฌดํจํ๋ฏ๋ก ๋ ์ด์ ๊ณ์ฐ์ ์งํํ๋ฉด ์๋๊ธฐ ๋๋ฌธ์ด๋ค.
ํ์๋ ํด๋น ๊ณ์ฐ์ ์ํด HashMap์ ํ์ฉํ๋ค.
ํด์๋งต์ ๋ช
๋ถ ๊ฐ์ ๊ฒ์ด๋ค. (๊ฐ ์ฝ์
์ ๋ฑ๋ก, ๊ฐ ์ญ์ ์ ์ญ์ ) ์ด๋ฅผ ํตํด, ๋ ๊ฐ์ ํ ์ค ์ด๋ ๊ณณ์์๋ผ๋ ์ญ์ ๋๋ฉด ํด์๋งต ๋ช
๋ถ์์๋ ์ญ์ ํ๋ค. ๋ง์ฝ ์ด๋ฏธ ํด์๋งต ๋ช
๋ถ์ ์๋ ๊ฐ์ด๋ผ๋ฉด, ๋ฌดํจํ ๊ฐ์ด๋ฏ๋ก, ์ต๋๊ฐ์ด๋ ์ต์๊ฐ์ ๋ค์ poll()ํ๋ค.
(1) ์๊ฐ๋ณต์ก๋ ๋ถ์ โณ
์ ์ผ ๋ง์ ์ฐ์ฐํ์๊ฐ operation ๋ฐฐ์ด์ ํ ๋ฐํด ๋๋ ๊ฒ์ธ๋ฐ, ํด๋น ๋ฐฐ์ด์ ๊ธธ์ด๋ $1,000,000$ ์ด๋ฏ๋ก, ์๊ฐ ์ด๊ณผ ๊ฑฑ์ ์ ์๋ค.
3. ์ฝ๋ ๐
(1) SUDO CODE ๐ฌ
0. ์๋ฃ๊ตฌ์กฐ ์ธํ
: ์ฐ์ ์์ ํ 2๊ฐ(๋ด๋ฆผ์ฐจ์, ์ค๋ฆ์ฐจ์), ํด์๋งต (๋ช
๋ถ ์์ฑ์ฉ)
1. ๋ค์์ ๋ฐ๋ผ ๋ช
๋ น์ด๋ฅผ ํ๋์ฉ ์ฐ์ฐํ๋ค.
1. ์ฝ์
๋ช
๋ น์ด๋ฉด, ๋ ๊ฐ์ ํ์ ํด์๋งต์ ๊ฐ์ ์ฝ์
ํ๋ค.
2. ์ต๋๊ฐ ์ญ์ ๋ช
๋ น์ด ์ด๋ฉด, HashMap ๋ช
๋ถ์ ์กด์ฌํ๋ ๊ฐ์ ๋ง๋ ๋๊น์ง poll()ํ๋ค.
3. ์ต์๊ฐ ์ญ์ ๋ช
๋ น์ด๋ ๋๊ฐ์ด HashMap ๋ช
๋ถ์ ์กด์ฌํ๋ ๊ฐ์ ๋ง๋ ๋๊น์ง poll() ํ๋ค.
2. ๋ช
๋ถ๋ฅผ ์ ๋ถ ๋ ๋ค์๋ ๋์ sync๋ฅผ ๋ง์ถ์ด์ผ ํ๋ค. ์๋ํ๋ฉด ์ญ์ ๋ช
๋ น์ด๊ฐ ์ต๋๊ฐ ์ญ์ ๋ ์ต์๊ฐ ์ญ์ ์ค ํ๋๋ก ์น์ฐ์น ๊ฒฝ์ฐ, ์์ ์ฐ์ฐ ๊ณผ์ ์ด ๋๋๊ณ , ๋์ sync๊ฐ ์ ๋ง์์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
1. 1๋ฒ์ 2์ 3๋ฒ์ ๋ฐ๋ณตํ๋ค.
3. ํ์ ๊ฐ์ด ๋จ์์์ผ๋ฉด ๊ทธ๊ฒ๋ค์ peek()์ ์ถ๋ ฅ, ์๋๋ฉด `[0,0]` ์ ์ถ๋ ฅํ๋ค.
(2) JAVA CODE โ
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> (b-a));
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a,b) -> (a-b));
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < operations.length; i++){
StringTokenizer st = new StringTokenizer(operations[i]);
char order = st.nextToken().charAt(0);
int value = Integer.parseInt(st.nextToken());
switch (order) {
case 'I': {
maxHeap.add(value);
minHeap.add(value);
map.put(value, value);
break;
}
case 'D': {
PriorityQueue<Integer> now;
if(value == 1){
now = maxHeap;
}else {
now = minHeap;
}
while(now.size() > 0){
int out = now.poll();
if(map.get(out) != null){
map.remove(out);
break;
}
}
break;
}
}
}
while(maxHeap.size() > 0){
int peek = maxHeap.peek();
if(map.get(peek) == null) maxHeap.poll();
else break;
}
while(minHeap.size() > 0) {
int peek = minHeap.peek();
if(map.get(peek) == null) minHeap.poll();
else break;
}
if(maxHeap.size() == 0 && minHeap.size() == 0) return new int [] {0,0};
else return new int [] {maxHeap.peek(), minHeap.peek()};
}
}
4. ํธ๋ฌ๋ธ ์ํ or ๋ฐฐ์ด ์ ๐
- ์์