각 묶음의 카드의 개수가 A, B 라고 주어질 때, 한 번 두 묶음을 합칠 때 A+B 번의 비교를 해야한다. 만약 A, B, C, D 의 카드 개수를 순서대로 하나로 합치려고 할 때, (A+B) + ((A+B)+C) + ((A+B+C)+D) 번 총 비교해야 한다.
카드의 개수가 연속으로 주어질 때, 최소한 몇 번 비교해야 하는지 알아내시오.
2.문제예제
3.문제풀이(수동)
주어진 문제예제를 살펴보면, (10+20) 번 비교하고, 다시 그 묶음을 40 번과 비교해서 (10+20) + (30+40) 번 비교해야 한다. 정렬이 되어 있지 않는 경우도 살펴볼 수 있다. 10, 20, 28, 25 라면, (10+20) 번 비교하고, (28+25) 번 비교한 다음 두 카드비교를 더해 (10+20) + (28+25) + (10+20) + (28+25) 로 최소 166 번 비교할 수도 있다.
4.팩트추출
Fact 1: 한 번 합쳐진 값도 다시 하나의 값으로 인식해서 나머지 다른 값들과 비교해 최소끼리 계속 더해야 한다.
문제풀이(수동) 두 번째 예제를 보면 10+20 번 비교해서 한 번 합쳐진 값이 다른 값들과 비교하는데 나머지 25, 28 숫자보다 커서 25와 28끼리 합쳐야 한 것을 볼 수 있다.
Fact 2: Fact 1 번을 통해 연산한 결과 값들도 나머지 다른 값들과 함께 정렬되어 다시 연산에 쓰여야 된다는 것을 알 수 있다. 다시 말해보면, 삽입하면서 정렬이 되고 그 중 항상 최소값을 가져와야 한다.
5.문제전략
Fact 2 번을 통해 연산한 결과 값이 삽입하면서 정렬이 되어야 하고, 항상 최소값을 가져와야 한다는 점 때문에 우선순위 큐를 사용하면 된다.
5.소스코드
import java.io.*;
import java.util.PriorityQueue;
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());
long total = 0;
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
long cardValue = Long.parseLong(br.readLine());
pq.add(cardValue);
}
while (pq.size() > 1) {
long first = pq.poll();
long second = pq.poll();
total += first + second;
pq.add(first + second);
}
System.out.println(total);
}
}
집과 사무실의 시작점, 끝점과 주어진 길이 d 가 주어질 때, 길이 d 에 포함되는 집과 사무실 구간의 개수가 최대인 경우를 구하시오.
2.문제예제
3.문제풀이(수동)
예제들을 문제풀이하면서 아이디어를 얻을 수는 없다. 아래 팩트추출을 통해 모든 경우의 수를 점검해야 한다.
4.팩트추출
Fact 1: 범위가 포함이 되어있는지 확인할 때, 나머지 좌표들을 정렬하면 다른 한 쪽만 대소비교할 수 있어 복잡도를 줄일 수 있다. 아래는 구간들의 오른쪽 끝점을 기준으로 오름차순으로 정렬한 모습이다. 가장 아래쪽부터 1번, 2번, 3번이라고 지칭할 때 다양한 특징들이 발견된다.
먼저 1번을 기준으로 2번이 포함되지 않는다면 3번, 4번에서도 2번은 포함되지 않는다. (오른쪽 끝점이 계속 순차적으로 증가하는 형태이기 때문에) 한 번 제외된 구간은 다른 구간에서 계산할 때도 제외된다는 뜻이다.
Fact 2 : 거리 N 에 포함되지 않는 구간은 계산할 필요가 없다.
Fact 3: 이전 결과에서는 거리 N 에 포함이 되었더라도 다음에 계산할 때는 오른쪽 끝점이 이동하므로 포함되지 않을 수 있다. 이전 결과를 활용하기 위해 시작점도 정렬이 필요하다. 거리 N 에 포함되면 시작점을 포함했다가 오른쪽 끝점이 이동할 때 정렬되어 있는 시작점들에서 하나씩 꺼내 비교하면 모두 다 비교하지 않아도 된다.
5.문제전략
한 쪽을 정렬해서 이전 결과 값을 재활용해야 한다는 점, 다른 한 쪽도 삽입을 하면서 정렬을 해야한다는 점을 파악해야 한다. 삽입하면서 정렬하는 자료구조는 우선순위큐가 적절하다.
5. 소스코드
private static class Interval implements Comparable<Interval> {
int start, end;
Interval(int startVariable, int endVariable) {
start = startVariable;
end = endVariable;
}
@Override
public int compareTo(Interval o) {
return Integer.compare(this.end, o.end);
}
}
public static void main(String[] args) {
// 거리 N, Interval 은 집과 구간, 오른쪽 끝점으로 정렬
// ... (생략) ...
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (Interval interval : intervals) {
if (interval.start >= interval.end - N) {
count++;
pq.add(interval.start);
}
while (!pq.isEmpty() && pq.peek() < interval.end - N) {
pq.poll();
count--;
}
maximum = Math.max(maximum, count);
}
}
횡단보도에 파란불이 들어오면 반대편 지역으로 이동할 수 있으며 이동하는 데 1분이 걸린다. 1 + i ( 0 <= i < M) 번째 신호는 i, M+i, 2M+i, 3M+i, ... 분 주기에 시작해서 1분 동안 Ai 번 지역과 Bi 번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.
횡단보도와 신호의 정보가 주어질 때, 시간 0 분에서 시작해서 1 번 지역에서 N 번 지역까지 가는 최소 시간을 구하시오.
2.문제예제
3.문제풀이(수동)
예제 풀이 2번을 수동 풀이한다.
구간
시간
3 - 4
1분, 13분, 25분, 37분...
5 - 6
2분, 14분, 26분, 38분...
7 - 8
3분, 15분, 27분, 39분...
2 - 3
4분, 16분, 28분, 40분...
1 - 5
5분, 17분, 29분, 41분...
...
... (생략) ...
각 횡단보도가 켜지는 시간대는 위 표와 같다. 내가 만약 7 - 8 번 구간을 처음에 선택하였다면 그 다음 구간을 선택할 때 걸리는 시간이 시계방향처럼 연산된다. 그 다음 1 - 5 번 구간을 선택하면 +2 가 되고, 3 - 4 번 구간을 선택하면 한 바퀴 돌아서 +10 이 된다. 그 다음 구간의 시간 대가 현재 시간 대보다 적다면 한 바퀴 돌아서 연산된다.
W x H 크기의 직사각형 감옥이 있다. 이 감옥에는 두 명의 죄수가 있는데 이 두 죄수를 탈출시키기 위해서 열어야 하는 문의 최소 개수값은 얼마인지 구하시오. 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다. 문은 한 번 열리면 계속 열린 상태가 된다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다. (죄수 - 감옥 - 죄수 모두 연결 상태)
2.문제예제
3.팩트추출
Fact 1: Dijkstra 알고리즘 문제처럼 보인다. 그런데 출발지가 두 군데이고, 두 군데에서 같이 움직이면 BFS 의 경로 정보가 변질되어 버린다. [Programmers] 등산 코스 정하기 (Java) :: 골드에그 (tistory.com) 문제 같은 경우는 어디서 출발하던지 산봉우리에 도달하는 최소 경로만 찾으면 되므로 같이 움직여도 상관 없지만, 이 문제는 두 사람이 같은 경로로 탈출해야 한다는 점이 다르다.
같이 움직일 수 없다면 따로 움직여서 정보를 합쳐야 하는데 어떤 정보를 기준으로 합쳐야 할까?
어떠한 지점에서 BFS 최소 결과 값을 합친다면, 그 의미는 두 사람이 그 지점으로 만나기 위한 최소 값이다.
위 예제에서는 A 에서 1 로 가는 최소의 경로가 1 이고 B 에서 1 로 가는 최소의 경로가 2 인 것이다. A 와 B 가 만나기 위한 최소 값이라고 해석할 수 있다. 그런데 이 정보만으로는 부족하다. 탈출하기 위한 루트가 포함되지 않았다. A 와 B 는 만났지만, 탈출하기 위한 최소값이라고 볼 수는 없다.
탈출하기 위한 경로를 계산하려면, 탈출구에서 해당 지점까지 가는 경로도 추가해야 한다.
모든 경로가 최소가 되려면, A 에서 1 지점까지 거리도, B 에서 1 지점까지 거리도, 1 지점에서 탈출구까지 거리도 모두 최소여야 하기 때문이다. 만나는 지점을 중심으로 생각해보면 쉽다.
Fact 2: 탈출구에 대한 정보를 맵 입력을 받을 때 알 수 없으므로 원래 맵 크기보다 1사이즈 더 크게 만들어 탈출구에서 오는 길목을 만들어준다. 원래 맵 크기가 N X M 이라면 N+2 X M+2 크기의 맵에서 시작한다.
Fact 3 :정보를 합칠 때 중요한 점은 중복 정보를 제거해야 한다는 것이다. 1 지점까지 가는데 어떤 정보들이 중복이 되는지 생각해보아야 한다. 지문에서 문이 한 번 열리면 계속 열린 상태가 된다고 하였으므로 세 정보를 합칠 때 문에서 중복 카운트는 빼주어야 한다. 여기서는 세 명이 만난다고 가정해도 되므로 -2 를 해주면 된다.
4.문제풀이(수동)
위 팩트추출을 통해 알아본 알고리즘으로 첫 번째 예제를 풀어보면 다음과 같다.
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
(출처 : BOJ 9376 · 탈옥 — PROJECT REBAS)
5.문제전략
문제 전략은 팩트 추출과 문제 풀이를 통해 알아보았다. 원래 맵 크기보다 한 사이즈 큰 맵을 준비하고, 탈출구에서 오는 최소 DFS 결과 값과 각 죄수들로부터 DFS 한 결과 값을 합쳐 최소 경로를 구한다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int row, column;
private static char[][] map;
private static Node[] prisoners;
private static final int[] dx = { 0, 0, -1, 1 };
private static final int[] dy = { 1, -1, 0, 0 };
private static final char WALL = '*';
private static final char DOOR = '#';
private static final char PRISONER = '$';
static class Node implements Comparable<Node>{
int x, y, open;
Node(int x, int y) {
this.x = x;
this.y = y;
this.open = 0;
}
Node(int x, int y, int open) {
this.x = x;
this.y = y;
this.open = open;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.open, o.open);
}
}
private static int[][] bfs(Node start) {
PriorityQueue<Node> queue = new PriorityQueue<>();
int[][] visited = new int[row+2][column+2];
for (int[] visit: visited) {
Arrays.fill(visit, -1);
}
queue.offer(start);
visited[start.x][start.y] = 0;
while(!queue.isEmpty()) {
Node current = queue.poll();
for (int i = 0; i < 4; i++) {
int neighborX = current.x + dx[i];
int neighborY = current.y + dy[i];
if(neighborX < 0 || neighborX >= row+2 || neighborY < 0 || neighborY >= column+2) continue;
if(visited[neighborX][neighborY] != -1 || map[neighborX][neighborY] == WALL) continue;
if(map[neighborX][neighborY] == DOOR) {
visited[neighborX][neighborY] = visited[current.x][current.y] + 1;
queue.offer(new Node(neighborX, neighborY, current.open + 1));
} else {
visited[neighborX][neighborY] = visited[current.x][current.y];
queue.offer(new Node(neighborX, neighborY, current.open));
}
}
}
return visited;
}
private static int getSum(int[][] one, int[][] two, int[][] out) {
int minSum = row * column;
for (int i = 0; i < one.length; i++)
{
for (int j = 0; j < one[i].length; j++)
{
if (map[i][j] == WALL)
continue;
if (one[i][j] == -1 && two[i][j] == -1 && out[i][j] == -1)
continue;
int sum = one[i][j] + two[i][j] + out[i][j];
if (map[i][j] == DOOR)
{
sum -= 2;
}
if (minSum > sum)
{
minSum = sum;
}
}
}
return (minSum);
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
while(testCase-- > 0) {
st = new StringTokenizer(br.readLine());
row = Integer.parseInt(st.nextToken());
column = Integer.parseInt(st.nextToken());
map = new char[row+2][column+2];
int[][] prisonerOne, prisonerTwo, out;
prisoners = new Node[2];
int prisonersIndex = 0;
for (int i = 0; i < row; i++) {
char[] row = br.readLine().toCharArray();
for (int j = 0; j < column; j++) {
if (row[j] == PRISONER) {
prisoners[prisonersIndex++] = new Node(i + 1, j + 1);
}
map[i+1][j+1] = row[j];
}
}
out = bfs(new Node(0,0));
prisonerOne = bfs(prisoners[0]);
prisonerTwo = bfs(prisoners[1]);
System.out.println(getSum(prisonerOne, prisonerTwo, out));
}
}
}
각 문제마다 조건이 추가된다. 이 이항계수 시리즈는 수학적인 사고력을 높이고 특히 모듈러 연산에 대해 깊게 생각할 수 있게 해주는 문제들이다.
이항 계수 (1)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static long factorial(long n) {
long result = 1;
while(n > 1) {
result = (result * n);
n--;
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long N = Long.parseLong(st.nextToken());
long R = Long.parseLong(st.nextToken());
long first = factorial(N);
long second = factorial(R) * factorial(N-R);
System.out.println(first / second);
}
}
이항 계수 (2)
이항 계수 (3)
+ 이항 계수 결과 값을 특정 숫자로 나누었을 때 나머지를 출력해야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private final static long P = 1000000007;
private static long factorial(long n) {
long result = 1;
while(n > 1) {
result = (result * n) % P;
n--;
}
return result;
}
private static long pow(long base, long exponent) {
long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result *= base;
result %= P;
}
base = (base * base) % P;
exponent /= 2;
}
return result;
}
/*
* [*] nCr mod P = n! / r! (n-r)! mod P
* = n! * (r! * (n-r)!)^-1 mod P ( ※ 나눗셈에 대한 mod 연산은 없으므로 곱하기 연산으로 바꾸어 준다. )
* = ( n! mod P * (r! * (n-r)!)^-1 mod P ) mod P ( ※ 곱셈에 대한 mod 연산으로 바꾸어 준다. )
*
* [*] 페르마 정리 a^p mod p = a mod p 응용하여 a mod p 의 역원 구하기
* = a^p-1 mod p = 1 mod p ( ※ 양 쪽에 a^-1 를 곱하였다. )
* = a * a^p-2 mod p = 1 mod p 이므로 a mod p 의 역원은 a^p-2 mod p 이다.
*
* = ( n! mod P * (r! * (n-r)!)^p-2 mod P ) mod P ( ※ a mod p 의 역원으로 바꾸어 준다. )
* */
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long N = Long.parseLong(st.nextToken());
long R = Long.parseLong(st.nextToken());
long first = factorial(N);
long second = pow(factorial(R) * factorial(N-R) % P, P-2);
System.out.println(first * second % P);
}
}
R x C 직사각형 모양의 호수가 존재한다. 이 호수에는 백조가 두 마리 존재하는데 빙판이 있어 서로 만날 수 없다. 하루가 지날 때마다 물에 인접한 빙판들은 모두 녹는다고 할 때 며칠이 지나야 백조 두 마리가 만날 수 있는지 구하시오.
2.문제예제
3.문제풀이(수동)
전형적인 BFS 문제로 수동 풀이는 진행하지 않는다. 지문에서 언급한 내용처럼 물에 인접한 빙판들은 모두 녹는다.
녹을 때 두 백조가 만날 수 있는지만 체크하면 된다.
4.팩트추출
Fact 1: 전형적인 BFS 문제이다. 한 번 맵을 훑으면서 빙판을 녹이고, 백조가 서로 만나는지 다시 맵을 훑으면 된다. 단순 BFS 구현 문제라고 생각이 들지만, R 과 C 가 무려 1500 으로 한 번 맵을 탐색할 때마다 1500 * 1500 시간복잡도가 발생한다. 그것도 빙판을 녹일 때 한 번, 백조가 서로 만나는지 확인하기 위해 한 번 수행하면 총 1500 * 1500 * 2 시간복잡도가 된다. 조금 더 효과적으로 BFS 를 수행해야 한다.
Fact 2:백조 중심으로 BFS 를 수행하면 빙판을 만나거나 백조를 만나거나 두 가지 경우를 만나게 된다. 백조를 만나면 그 동안에 계산된 day 를 리턴하면 되고, 빙판을 만났다면 그 빙판들을 기억하기 위해 모두 큐에 담아 그 큐에서부터 다시 시작하면 된다. 빙판을 녹이기 위한 BFS 는 따로 수행해서 서로 영향을 미치지 않게 동작시킨다. 따라서, Water 에 대한 큐, 다음 검색을 위한 큐가 필요하다.
5.문제전략
문제 전략은 팩트 추출을 통해 알아보았다. 백조 중 하나부터 시작해서 dfs 를 수행하고 빙판을 만나면 그 지점들을 기억했다가 다시 그 부분부터 dfs 를 시작하면 된다. 다시 dfs 를 시작하기 전 빙판이 녹아야 하므로 빙판에 대한 dfs 를 한 번 수행한다.
6.소스코드
package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int R, C;
private static Node[] swan;
private static char[][] map;
private static Queue<Node> queue, waterQueue;
private static boolean[][] visited;
private static final int[] dr = { -1, 1, 0, 0 };
private static final int[] dc = { 0, 0, -1, 1 };
private static int day = 0;
static class Node {
int r, c;
Node(int r, int c) {
this.r = r;
this.c = c;
}
}
private static void waterBFS() {
// 한 번만 녹여야 하므로, 현재 큐 사이즈만큼만 돌린다.
int waterSize = waterQueue.size();
while (waterSize-- > 0) {
Node now = waterQueue.poll();
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0) continue;
if (map[nextR][nextC] == 'X') {
map[nextR][nextC] = '.';
waterQueue.offer(new Node(nextR, nextC));
}
}
}
}
private static void BFS() {
boolean meet = false;
while (true) {
Queue<Node> nextQueue = new LinkedList<>();
while (!queue.isEmpty()) {
Node now = queue.poll();
if (now.r == swan[1].r && now.c == swan[1].c) {
meet = true;
break;
}
for (int i = 0; i < 4; i++) {
int nextR = now.r + dr[i];
int nextC = now.c + dc[i];
if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0 || visited[nextR][nextC]) continue;
visited[nextR][nextC] = true;
if (map[nextR][nextC] == 'X') {
nextQueue.offer(new Node(nextR, nextC));
continue;
}
queue.offer(new Node(nextR, nextC));
}
}
if (meet) break;
queue = nextQueue;
waterBFS();
day++;
}
return;
}
public static void main(String[] args) throws IOException {
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
swan = new Node[2];
queue = new LinkedList<>();
waterQueue = new LinkedList<>();
visited = new boolean[R][C];
int swanIndex = 0;
for (int i = 0; i < R; i++) {
char[] line = br.readLine().toCharArray();
for (int j = 0; j < C; j++) {
map[i][j] = line[j];
if(map[i][j] == 'L') {
swan[swanIndex++] = new Node(i, j);
}
if(map[i][j] != 'X') {
waterQueue.offer(new Node(i, j));
}
}
}
queue.offer(swan[0]);
visited[swan[0].r][swan[0].c] = true;
BFS();
System.out.println(day);
}
}
정수를 하나씩 외칠 때마다 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 현재까지 모은 숫자의 갯수가 짝수 개라면 중간에 있는 두 수 중에서 짝수를 말해야 한다.
2.문제예제
3.문제풀이(수동)
위 문제 예제 입력 1번에 대해서 문제풀이한다.
숫자를 하나씩 받을 때마다 정렬하여 중간에 있는 숫자를 출력하면 된다. 숫자가 짝수 개일때는 둘 중에 작은 숫자를 출력한다.
1 => 1
1, 5 => 1 (짝수이므로 둘 중에 작은 숫자)
1, 5, 2 => 2
1, 5, 2, 10 => 2 (짝수이므로 둘 중에 작은 숫자)
-99, 1, 2, 5, 10 => 2
-99, 1, 2, 5, 7, 10 => 2(짝수이므로 둘 중에 작은 숫자)
-99, 1, 2, 5, 5, 7, 10 => 5
4.팩트추출
Fact 1: 숫자를 받을 때마다 그 리스트를 정렬하여 중간 값을 가지고 오면 문제는 쉽게 풀린다. 다만 지문에서 확인할 수 있듯이, 아래와 같이 N 이 최대 100,000 이며, 받을 때마다 정렬하면 매번 O(N) 시간이 소요된다. 이러면 시간제한인 0.1초를 해결할 수 없을 것이다. 0.1초라는 시간을 만족하려면 삽입할 때마다 정렬하는 시간도 줄여야 하고 중간 값을 탐색하는 시간도 줄여야 한다. 정렬, 탐색 시간을 모두 줄여야 한다.
Fact 2: 아래 사이트에서 자바 Collection 들에 대한 시간복잡도를 모두 찾아보았다.
이 자료구조들에서 아이템을 삽입했을 때 자동정렬해주는 자료구조는 PriorityQueue 밖에 없다. O(log N) 으로 삽입과 동시에 정렬을 하기 때문에 빠르게 수행할 수 있다. 그리고 중간 값을 찾아주는 메서드는 어느 자료구조에도 없다. 결국 탐색해야 한다. Priority Queue 의 peek O(1) 시간 복잡도를 활용할 수 있는 방안은 없을까?
Priority Queue 의 peek 은 우선순위가 가장 높은 아이템 하나를 뽑으므로 중간에 peek 을 가리킬 수 있도록 Priority Queue 를 두 개 준비한다면 중간값을 바로 찾을 수 있을 것이다. 우선순위는 서로 반대이므로 왼쪽이 Max Heap, 오른쪽이 Min Heap 이 되어야 한다. Max Heap 은 내림차순으로 정렬되어 있는 자료구조로 가장 큰 값이 우선순위가 높고, Min Heap 은 오름차순으로 정렬되어 있는 자료구조로 가장 작은 값이 우선순위가 높다.
매번 삽입할 때마다 정렬하므로 maxHeap 의 peek 은 절반 중 가장 큰 값이고, minHeap 의 peek 은 절반 중 가장 작은 값이다. 아이템을 minHeap 에 넣든 maxHeap 에 넣든 상관없지만, 위 구조를 만족시키려면 minHeap 의 최소값이 maxHeap 의 최대값보다 항상 크도록 만들어주어야 한다. 넣고 나서 비교하고 maxHeap peek 숫자가 크다면 바꾸어 주면 된다.
5.문제전략
문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. minHeap 과 maxHeap 을 절반씩 만들어 값을 번갈아 가며 넣고 peek 으로 중간값을 꺼낸다.
6.소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for(int i = 0 ; i < n; i++){
int num = Integer.parseInt(br.readLine());
if(minHeap.size() == maxHeap.size()) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
if(!minHeap.isEmpty() && !maxHeap.isEmpty())
if(minHeap.peek() < maxHeap.peek()){
int tmp = minHeap.poll();
minHeap.offer(maxHeap.poll());
maxHeap.offer(tmp);
}
sb.append(maxHeap.peek() + "\n");
}
System.out.println(sb);
}
}
