μ΄μ€ μ°μ μμ νλ λ€μ μ°μ°μ ν μ μλ μλ£κ΅¬μ‘°λ₯Ό λ§ν©λλ€.
λͺ λ Ήμ΄ | μμ ν(λμ΄) |
---|---|
I μ«μ | νμ μ£Όμ΄μ§ μ«μλ₯Ό μ½μ ν©λλ€. |
D 1 | νμμ μ΅λκ°μ μμ ν©λλ€. |
D -1 | νμμ μ΅μκ°μ μμ ν©λλ€. |
μ΄μ€ μ°μ μμ νκ° ν μ°μ° operationsκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, λͺ¨λ μ°μ°μ μ²λ¦¬ν ν νκ° λΉμ΄μμΌλ©΄ [0,0] λΉμ΄μμ§ μμΌλ©΄ [μ΅λκ°, μ΅μκ°]μ return νλλ‘ solution ν¨μλ₯Ό ꡬνν΄μ£ΌμΈμ.
operations | return |
---|---|
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] | [0,0] |
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] | [333, -45] |
λ°λΌμ [0, 0]μ λ°νν©λλ€.
μ΄μ€ μ°μ μμ νμ -45, 45, 333μ΄ λ¨μμμΌλ―λ‘, [333, -45]λ₯Ό λ°νν©λλ€.
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
// μ΅μ ν μμ±
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// μ΅λ ν μμ±
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (String operation : operations) {
// 곡백μ κΈ°μ€μΌλ‘ λΆλ¦¬
String[] temp = operation.split(" ");
// λͺ
λ Ήμ΄ "I"μΈ κ²½μ° κ°κ°μ μ°μ μμ νμ μΆκ°
if (temp[0].equals("I")) {
minHeap.add(Integer.parseInt(temp[1]));
maxHeap.add(Integer.parseInt(temp[1]));
}
else if (!maxHeap.isEmpty() && temp[0].equals("D") && temp[1].equals("1")) {
int max = maxHeap.poll();
minHeap.remove(max);
}
else if (!minHeap.isEmpty() && temp[0].equals("D") && temp[1].equals("-1")) {
int min = minHeap.poll();
maxHeap.remove(min);
}
}
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
answer[0] = 0;
answer[1] = 0;
}
else {
answer[0] = maxHeap.poll();
answer[1] = minHeap.poll();
}
return answer;
}
}
μ΄ λ¬Έμ μμλ μ΅μκ°κ³Ό μ΅λκ°μ λμμ λ€λ£¨μ΄μΌ νκΈ° λλ¬Έμ,
μ°μ μ΅μ νκ³Ό μ΅λ νμ κ°κ° μμ±ν΄ μ£Όμλ€.
μ΄μ operations
λ°°μ΄μ μ²λ¦¬ν μ°¨λ‘μ΄λ€.
operations
μλ I μ«μ
, D 1
, D -1
μ€ νλμ κ°μ΄ μμλ‘ λ€μ΄κ° μκΈ° λλ¬Έμ, μ΄μ λ°λ₯Έ 쑰건μ λΆλ¦¬ν΄ μ£Όμ΄μΌ νλ€.
κ·Έλ¬κΈ° μν΄ κ³΅λ°±μ κΈ°μ€μΌλ‘ μΌλ¨ λ¬Έμμ΄μ λΆλ¦¬ν΄ μ κΈμκ° I
μΈ κ²½μ°, μ κΈμκ° D
μ΄κ³ λ· κΈμκ° 1
μΈ κ²½μ°, μ κΈμκ° D
μ΄κ³ λ· κΈμκ° -1
μΈ κ²½μ°λ‘ λλμ΄ μ£Όμλ€.
μ¬κΈ°μ λ§μ½ 첫 λ²μ§Έ 쑰건μΌλ‘ λ€μ΄κ°κ² λμμ λ, κ°κ°μ μ°μ μμ νμ λ€μ μ€λ μ«μλ₯Ό μΆκ°ν΄μ£Όμλ€.
λ§μ½ λ λ²μ§Έ 쑰건μΌλ‘ λ€μ΄κ°κ² λμμ λ, μ¦, μ΅λκ°μ μμ ν΄μΌ νκΈ° λλ¬Έμ, μ΅λ ν maxHeap
μμ poll()
ν¨μλ₯Ό μ¬μ©ν΄ μ΅λκ°(λ£¨νΈ λ
Έλ)λ₯Ό μΆμΆ ν μ κ±°ν΄ μ£Όμλ€.
μ¬κΈ°μ, μ΅μ νμλ ν΄λΉ κ°μ μ κ±°ν΄ μ£Όμ΄μΌ νκΈ° λλ¬Έμ, remove
ν¨μλ₯Ό μ¬μ©ν΄ μ΅λκ°μ μ κ±°ν΄ μ£Όμλ€.
μΈ λ²μ§Έ 쑰건μΌλ‘ λ€μ΄κ°κ² λμμ λλ μ΅μκ°μ μμ ν΄μΌ νκΈ° λλ¬Έμ, μ΅λκ°μ μ κ±°νλ λ°©μκ³Ό λ§μ°¬κ°μ§λ‘ μ΅μ νμμ λ£¨νΈ λ Έλλ₯Ό μ κ±°νκ³ , μ΅λ νμλ ν΄λΉ κ°μ μ κ±°ν΄ μ£Όμλ€.
μ΄μ λ§μ§λ§ 쑰건μ μ²λ¦¬ν΄μΌ νλ€.
λͺ¨λ μ°μ°μ μ²λ¦¬ν ν νκ° λΉμ΄μμΌλ©΄, [0, 0]μ λ°νν΄μΌ νκΈ° λλ¬Έμ, ν΄λΉ 쑰건문μ λ§λ€μ΄ μ²λ¦¬λ₯Ό ν΄μ£Όμκ³ ,
νκ° λΉμ΄μμ§ μμΌλ©΄, μ΅μ’
μ μΌλ‘ μ΅λκ°κ³Ό μ΅μκ°μ κ°κ° λ°νν΄ μ£Όμ΄μΌ νκΈ° λλ¬Έμ,
κ°κ°μ μ°μ μμ νμμ λ£¨νΈ λ
Έλλ₯Ό μΆμΆν΄ answer
λ°°μ΄μ λ΄μμ λ°νν΄μ€μΌλ‘μ¨ λ¬Έμ λ₯Ό ν΄κ²°ν μ μμλ€!
ππμμμμ!