문제소개
[문제]
정수를 입력할 때마다 그때까지 입력된 정수 중 중앙값을 출력하는 문제다.
우선순위 큐(Priority Queue)를 활용하여 풀어야 한다. 자료구조에 대한 이해가 덜 된 상태에서 문제를 푸느라 뻘짓을 많이 했지만 그만큼 배운게 많다.
자료구조 간단 정리
| 자료구조 | 반환데이터 |
| 스택(Stack) | 제일 나중에 넣은 데이터(LIFO) |
| 큐(Queue) | 제일 처음 넣은 데이터(FIFO) |
| 우선순위 큐 (Priority Queue) | 가장 우선순위가 높은 데이터 |
스택과 큐는 입력과 출력을 다루는 것이 간단해보이지만 우선순위 큐는 그렇지 않다.
우선순위와 관계없이 값을 입력하지만 우선순위가 가장 높은 값을 출력해야 한다. 따라서 값을 입력할 때 기존의 값들과 우선순위를 비교하는 연산이 필요하다. 이때 힙을 이용한다.
힙은 트리구조를 가지는 자료구조인데, 자식노드가 둘 이하이다. 위에서 보는 것처럼 하위층이 상위층보다 우선순위가 높은 값을 가질수도 있다(3번째와 4번째). 하지만 자식노드는 무조건 부모노드보다 우선순위가 낮다.
특정 노드의 부모노드를 찾을 때는 해당 노드의 인덱스를 반으로 나눈 바닥값을 사용하고, 자식노드를 찾을 때는 인덱스에 2를 곱하면 된다.
이런 특징 덕에 힙은 배열로 간편히 표현할 수 있다.
새 노드는 제일 하위층의 제일 왼쪽에 채워지는데, 우선순위에 따른 배치를 할 때 전체 노드들과 비교하지 않고 부모노드와만 비교한다.
힙을 이용해 우선순위 큐를 구현하면 새 값을 입력할 때 빠른 배치가 가능하다.
자세한 구현은 정답 풀이에 있다.
오답(시간초과)
[시간초과난 풀이는 관심없고, 풀린것부터 볼래요.]
처음 생각한 답은 연결리스트이다(알고리즘 분류에서 우선순위 큐라는 것을 보고 풀었는데, 그때는 우선순위 큐가 뭐인지 몰라서 대충 연결리스트랑 비슷하겠지~ 하면서 풀었다. ㄱ-).
아래 과정을 거쳐 중앙값을 정한다.
- 중앙값보다 새로 들어온 값이 크면 값들을 중앙값의 이전값들을 훑으면서 위치를 찾아 넣는다. 반대도 마찬가지다.
- 새 값이 적절한 위치에 삽입되고 나면 중앙값을 적절히 이동한다.
결과적으로 풀리긴했지만 시간이 초과되었다.
우선순위 큐는 특정 집단에서 우선순위가 높은 것을 정할 때 이진 탐색(\( O(\log{n}) \))을 하는데 반해 연결리스트는 정확한 위치를 찾기 전까지 노드를 쭉 훑기(\( O(n) \)) 때문에 더 많은 시간을 잡아먹는듯 하다.
코드
전체 코드는 이렇다. 코드를 짤 때는 Linked List와 Queue를 그닥 제대로 인지하고 있지 않아서 클래스 명을 Queue라고 지었다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Queue {
Queue prev = null;
Queue next = null;
int value;
Queue(Queue prev, Queue next, int value) {
this.prev = prev;
this.next = next;
this.value = value;
}
void setNext(Queue next) {
next.prev = this;
if (this.next != null) {
next.next = this.next;
this.next.prev = next;
}
this.next = next;
}
void setPrev(Queue prev) {
prev.next = this;
if (this.prev != null) {
prev.prev = this.prev;
this.prev.next = prev;
}
this.prev = prev;
}
}
class Pointer {
Queue Q;
int index;
Pointer(Queue Q) {
this.Q = Q;
this.index = 1;
}
}
public class TimeOver {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int getNum() {
try {
return Integer.parseInt(br.readLine());
} catch (IOException e) {
return 0;
}
}
static void insertSmallerQueue(Queue current, Queue Q) {
if (current.prev == null) {
current.setPrev(Q);
return;
}
current = current.prev;
if (current.value < Q.value) {
current.setNext(Q);
return;
}
insertSmallerQueue(current, Q);
}
static void insertBiggerQueue(Queue current, Queue Q) {
if (current.next == null) {
current.setNext(Q);
return;
}
current = current.next;
if (current.value > Q.value) {
current.setPrev(Q);
return;
}
insertBiggerQueue(current, Q);
}
static void insertNewQueue(Queue current, Pointer center, int i) {
int n = getNum();
current = center.Q;
Queue Q = new Queue(null, null, n);
if (current.value > Q.value) {
insertSmallerQueue(current, Q);
if (i % 2 == 0) {
center.Q = center.Q.prev;
center.index -= 1;
}
} else {
insertBiggerQueue(current, Q);
if (i % 2 != 0) {
center.Q = center.Q.next;
center.index += 1;
}
}
}
public static void main(String[] args) {
int q = getNum();
int firstNum = getNum();
Queue current = new Queue(null, null, firstNum);
Pointer center = new Pointer(current);
try {
bw.write(center.Q.value + "\n");
for (int i = 2; i < q + 2; i++) {
insertNewQueue(current, center, i);
bw.write(center.Q.value + "\n");
bw.flush();
}
bw.close();
br.close();
} catch (IOException e) {}
}
}Pointer 클래스
연결리스트를 만들고 중앙값을 정하면서 중앙값 객체의 위치가 담긴 변수(center)를 함수로 넘기고, 함수에 center가 가리키는 객체를 다른 객체로 바꾸는 일을 시켰다.
Queue current = new Queue(null, null, firstNum);
Queue center = current
(...)
insertNewQueue(current, center, i);
bw.write(center.Q.value + "\n");
하지만 의도했던바와 달리 center은 함수에 들어가기 전과 같은 객체를 가리키고 있었다.
문제는 주소값은 call by reference가 아니라 call by value로 넘어가기 때문이었다. C에서 연결리스트를 만들어 봤으면서 Java에 포인터가 없다는 이유로 대강 넘어갔더니 이렇게 되었다.ㅋㅋ
함수에서 객체를 반환하게 해서 함수 밖에서 center에 다시 할당해줄까 고민하다가 그냥 Pointer 객체를 만들었다.
class Pointer {
Queue Q;
int index;
Pointer(Queue Q) {
this.Q = Q;
this.index = 1;
}
}
index 필드는 Pointer라는 이름에 맞지 않아서 class명을 바꿀까하다 어차피 단발성 코드라서 내버려뒀다.
Queue current = new Queue(null, null, firstNum);
Pointer center = new Pointer(current);
(...)
insertNewQueue(current, center, i);
bw.write(center.Q.value + "\n");
이제 center은 언제나 같은 객체를 가리키고, 함수는 center가 가리키는 객체를 조작한다.
Queue 클래스
이름은 Queue이지만 동작은 Linked List이다. 그냥 잘못 지은 이름이다. ㅇㅋㅇㅋ..
Queue prev = null;
Queue next = null;
int value;
이전 객체와 다음 객체, 값을 필드로 가진다.
Queue(Queue prev, Queue next, int value) {
this.prev = prev;
this.next = next;
this.value = value;
}
생성자에서 이전 객체, 다음 객체, 값을 설정한다.
void setNext(Queue next) {
next.prev = this;
if (this.next != null) {
next.next = this.next;
this.next.prev = next;
}
this.next = next;
}
다음 객체에 매개변수로 받은 객체를 넣는 메서드로, 만약 다음 객체가 기존에 존재하면 알맞게 연결해준다.
void setPrev(Queue prev) {
prev.next = this;
if (this.prev != null) {
prev.prev = this.prev;
this.prev.next = prev;
}
this.prev = prev;
}
이전 객체에 매게변수로 받은 객체를 넣는 메서드로, 동작은 위와 같다.
전체 동작
public static void main(String[] args) {
int q = getNum();
int firstNum = getNum();
Queue current = new Queue(null, null, firstNum);
Pointer center = new Pointer(current);
try {
bw.write(center.Q.value + "\n");
for (int i = 2; i < q + 2; i++) {
insertNewQueue(current, center, i);
bw.write(center.Q.value + "\n");
bw.flush();
}
bw.close();
br.close();
} catch (IOException e) {}
}
먼저 정수 개수를 입력받고, 첫 번째 정수는 반복문 밖에서 미리 할당해준다. 포인터는 첫번째 노드를 가리키도록 한다.
그 뒤 남은 정수 개수만큼을 반복문돌면서 insertNewQueue()함수를 통해 새로운 값을 정해진 위치에 넣고 중앙값을 재설정한 뒤 출력한다.
InsertNewQueue()
static void insertNewQueue(Queue current, Pointer center, int i) {
int n = getNum();
current = center.Q;
Queue Q = new Queue(null, null, n);
if (current.value > Q.value) {
insertSmallerQueue(current, Q);
if (i % 2 == 0) {
center.Q = center.Q.prev;
center.index -= 1;
}
} else {
insertBiggerQueue(current, Q);
if (i % 2 != 0) {
center.Q = center.Q.next;
center.index += 1;
}
}
}
insertNewQueue()에서는 현재 위치로 중앙값을 넣는다. 새로 입력받은 값으로 새로운 노드를 만들고 그 노드를 넣을 곳을 찾는다. 찾기는 중앙값을 기준으로 작을 경우와 클 경우로 나눠서 진행된다. 노드를 삽입한 후에는 상황을 보고 중앙값 포인터를 이동한다.
중앙값 포인터를 이동할 때 고려사항은 다음과 같다.
InsertSmallerQueue()
static void insertSmallerQueue(Queue current, Queue Q) {
if (current.prev == null) {
current.setPrev(Q);
return;
}
current = current.prev;
if (current.value < Q.value) {
current.setNext(Q);
return;
}
insertSmallerQueue(current, Q);
}
재귀호출을 이용하는 함수다.
만약 현재 노드의 이전 노드가 없으면 새로운 노드(Q)를 이전노드로 삽입하고 동작을 멈춘다.
그렇지 않은 경우 현재 노드를 그 이전 노드로 이동하고 이동한 노드의 값과 새로운 노드의 값을 비교한다. 이동한 노드의 값이 새로운 노드의 값보다 작으면 이동한 노드의 다음 값으로 새로운 노드를 끼워넣는다. 재귀호출은 여기서 끝난다.
이런 방식으로 중앙값보다 새로운 값이 작을 경우를 처리한다. 중앙값보다 큰 경우도 비슷하게 진행된다.
항상 현재노드가 새노드보다 큰 상태로 함수가 시작되기 때문에 이전노드가 없는 경우에 대소를 비교하지 않고 바로 할당할 수 있다.
이상 시간초과가 나온 코드의 설명이 끝났다.
정답
우선순위 큐를 두 개 둬서 해결하면 간단하다.
최대힙은 숫자가 클수록 우선순위가 높고, 최소힙은 숫자가 작을수록 우선순위가 높다.
최대힙에는 중앙값과 중앙값보다 작은 값을 저장하고 최소힙에는 중앙값보다 큰 값을 저장한다.
최대힙은 중앙값을 포함하기 때문에 언제나 최소힙과 크기가 같거다 1 크다. 절대 최소힙보다 작아질 수 없다.
크기에 의존해 값을 먼저 넣은 후 최대힙의 최상위노드와 최소힙의 최상위노드에 따라 각 힙의 최상위노드를 이동할지말지 결정한다.
이해하기 쉽게 이미지로 만들어봤다. 직접 만드니까 코드를 짜면서도 놓친 부분을 쉽게 눈치챌 수 있어서 좋다.
우선순위 큐 구현하기
전체코드다. int값만 받아들이도록 만들었지만 제네릭을 이용해 만들걸 싶다. 디폴트는 최대힙이며, 상속을 통해 최소힙으로 만들 수 있다.
class PQ {
private int heapSize;
private int[] itemHeap;
public PQ(int n) {
heapSize = 0;
itemHeap = new int[n + 1];
}
boolean compare(int a, int b) {
return a > b ? true : false;
}
public void add(int item) {
int i = ++heapSize;
while ((i != 1) && compare(item, itemHeap[i / 2])) {
itemHeap[i] = itemHeap[i / 2];
i /= 2;
}
itemHeap[i] = item;
}
public Integer peek() {
if (heapSize != 0)
return itemHeap[1];
return null;
}
public Integer poll() {
if (heapSize == 0)
return null;
int parent, child, item, temp;
item = itemHeap[1];
temp = itemHeap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize) {
if ((child < heapSize) && compare(itemHeap[child + 1], itemHeap[child]))
child++;
if (compare(temp, itemHeap[child]))
break;
itemHeap[parent] = itemHeap[child];
parent = child;
child *= 2;
}
itemHeap[parent] = temp;
return item;
}
public boolean isEmpty() {
if (heapSize == 0)
return true;
return false;
}
public int size() {
return heapSize;
}
}생성자와 필드
private int heapSize; // 힙 크기 = 현재 들어있는 노드의 개수
private int[] itemHeap; // 힙 노드들이 들어갈 배열
public PQ(int n) {
heapSize = 0;
itemHeap = new int[n + 1];
// 첫번째 인덱스는 비워놓기 때문에 개수 + 1로 초기화
}
필드로 힙 크기와 힙의 노드들이 담길 배열을 가진다.
배열의 경우 최상위 노드의 자식 계산을 위해 첫번째 값을 비워 최상위 노드의 인덱스가 1을 갖도록 한다. 이 때문에 들어갈 노드 개수 + 1으로 배열을 초기화 한다.
우선순위
boolean compare(int a, int b) {
return a > b ? true : false;
}
두 노드 간 우선순위를 비교하기 위한 메서드다. 이 클래스는 최대힙이 디폴트라서 첫 번째 노드가 더 클 경우 true를 반환한다. 최소힙을 구현할 때는 이 메서드를 오버라이드하면 된다.
노드 추가
public void add(int item) {
int i = ++heapSize;
while ((i != 1) && compare(item, itemHeap[i / 2])) {
itemHeap[i] = itemHeap[i / 2];
i /= 2;
}
itemHeap[i] = item;
}
우선 힙 크기를 늘린 뒤 그 인덱스(제일 하위)를 i에 저장한다. 그 뒤에 새노드(item)와 부모노드(itemHeap[i / 2])를 비교하여 새 노드의 우선순위가 더 높을 경우, 부모노드의 값을 i가 가리키는 위치에 붙여넣는다.
새 노드의 우선순위가 더 낮다면 i의 위치에 새 노드의 값 넣는다.
최상위 노드 반환
public Integer peek() {
if (heapSize != 0)
return itemHeap[1];
return null;
}
아무 값이 없으면 null을 반환하고 아니면 배열의 첫번째 값을 반환한다.
최상위 노드 반환 및 삭제
public Integer poll() {
if (heapSize == 0)
return null;
int parent, child, item, temp;
item = itemHeap[1];
temp = itemHeap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize) {
if ((child < heapSize) && compare(itemHeap[child + 1], itemHeap[child]))
child++;
if (compare(temp, itemHeap[child]))
break;
itemHeap[parent] = itemHeap[child];
parent = child;
child *= 2;
}
itemHeap[parent] = temp;
return item;
}
노드 추가보다 복잡한 이유는, 추가할 때는 부모와만 비교하면 되는데 삭제할 때는 스스로와 두 자식을 비교해야하기 때문이다. 즉 자식노드 둘 중에 더 큰 노드를 찾은 뒤, 부모노드와 비교해 더 큰 쪽을 부모노드 자리에 앉히는 것이다.
삭제하면서 제일 하위에 있던 노드를 최상위 노드로 만드는데(배열에 진짜 삽입하진 않고 그런 취급만 한다.) 이 명백하게 작은 노드는 더 큰 노드들을 위로 당겨오는 역할을 하게 된다.
상속으로 최소힙 구현
class MinPQ extends PQ {
MinPQ(int n) {
super(n);
}
@Override
boolean compare(int a, int b) {
return a < b ? true : false;
}
}
비교메서드만 덮어씌우면 된다.
메인 클래스
위의 이미지를 그대로 코드로 옮겼다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
PQ maxPQ = new PQ(N);
MinPQ minPQ = new MinPQ(N);
for (int i = 0; i < N; i++) {
int a = Integer.parseInt(br.readLine());
if (maxPQ.size() == minPQ.size()) {
maxPQ.add(a);
if (!minPQ.isEmpty() && maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
} else {
minPQ.add(a);
if (maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
}
bw.write(maxPQ.peek() + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class PQ {
private int heapSize;
private int[] itemHeap;
public PQ(int n) {
heapSize = 0;
itemHeap = new int[n + 1];
}
boolean compare(int a, int b) {
return a > b ? true : false;
}
public void add(int item) {
int i = ++heapSize;
while ((i != 1) && compare(item, itemHeap[i / 2])) {
itemHeap[i] = itemHeap[i / 2];
i /= 2;
}
itemHeap[i] = item;
}
public Integer peek() {
if (heapSize != 0)
return itemHeap[1];
return null;
}
public Integer poll() {
if (heapSize == 0)
return null;
int parent, child, item, temp;
item = itemHeap[1];
temp = itemHeap[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize) {
if ((child < heapSize) && compare(itemHeap[child + 1], itemHeap[child]))
child++;
if (compare(temp, itemHeap[child]))
break;
itemHeap[parent] = itemHeap[child];
parent = child;
child *= 2;
}
itemHeap[parent] = temp;
return item;
}
public boolean isEmpty() {
if (heapSize == 0)
return true;
return false;
}
public int size() {
return heapSize;
}
}
class MinPQ extends PQ {
MinPQ(int n) {
super(n);
}
@Override
boolean compare(int a, int b) {
return a < b ? true : false;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
PQ maxPQ = new PQ(N);
MinPQ minPQ = new MinPQ(N);
for (int i = 0; i < N; i++) {
int a = Integer.parseInt(br.readLine());
if (maxPQ.size() == minPQ.size()) {
maxPQ.add(a);
if (!minPQ.isEmpty() && maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
} else {
minPQ.add(a);
if (maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
}
bw.write(maxPQ.peek() + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
Java의 기본 라이브러리를 이용한 정답
속도차이는 거의 없다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
public class UsingLib {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> minPQ = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int a = Integer.parseInt(br.readLine());
if (maxPQ.size() == minPQ.size()) {
maxPQ.add(a);
if (!minPQ.isEmpty() && maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
} else {
minPQ.add(a);
if (maxPQ.peek() > minPQ.peek()) {
minPQ.add(maxPQ.poll());
maxPQ.add(minPQ.poll());
}
}
bw.write(maxPQ.peek() + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
끝
이틀동안 문제를 풀고 정리하는데도 오래걸린만큼 얻은게 많은 것 같다. 나름 머리가 나쁘지는 않다고 생각했는데 문제 푸는게 너무 어렵다.. 뇌가 많이 굳은 느낌이다.
'Programming > Algorithm' 카테고리의 다른 글
| [백준 12865] 평범한 배낭, 동적 계획법:Dynamic Programming (4) | 2022.03.16 |
|---|