๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/1655)
< ๊ฐ์ด๋ฐ๋ฅผ ๋งํด์ >
๋ฌธ์ ํ์ด
์ฐ์ ์์ ํ 2๊ฐ(left: ๋ด๋ฆผ์ฐจ์, right: ์ค๋ฆ์ฐจ์)๋ฅผ ์ฌ์ฉํด์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
์ฒ์์๋ left์ ๊ฐ์ ๋ฃ์ด์ค๋ค. ๊ทธ๋ค์ ๊ฐ์ ๋ณด๊ณ left queue์ ๋งจ ์์ ์๋ ๊ฐ ๋ณด๋ค ์์ ๊ฐ์ด๋ผ๋ฉด left queue์ ๋ฃ์ด์ค๋ค. ๋ง์ฝ right queue์ ๋งจ ์์ ์๋ ๊ฐ ๋ณด๋ค ํฌ๋ค๋ฉด right queue์ ๋ฃ์ด์ค๋ค.
๊ฐ์ด๋ฐ ๊ฐ์ ์ฐพ๋ ๊ฒ์ด๋ฏ๋ก ๊ฐ์ ๋ฃ์ ๋๋ง๋ค left์ right queue์ size ์ฐจ์ด๊ฐ 2 ์ด์ ๋๋ค๋ฉด 1 ์ฐจ์ด ๋๋ ๊ฐ๋๋ก ๋ง์ถฐ์ค๋ค.
๋ฌธ์ ์ ์ฃผ์ด์ง ์์๋๋ก 1, 5, 2, 10, -99, 7, 5๊ฐ ๋ค์ด์จ๋ค๊ณ ๊ฐ์ ํด ๋ณด์. ์๋์ ๊ฐ์ด ํํ๋๋๋ก ๊ตฌํํ๋ค.
my solution (Java)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
public class _1655_ { // ๊ฐ์ด๋ฐ๋ฅผ ๋งํด์
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bf.readLine());
PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> right = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(bf.readLine());
if (left.size() < 1) {
left.add(num);
} else {
if ((right.size()>0 && right.peek() >= num)|| left.peek()>=num)
left.add(num);
else
right.add(num);
if (left.size() - right.size() > 1) {
int temp = left.poll();
right.add(temp);
} else if (right.size() - left.size() > 1) {
int temp = right.poll();
left.add(temp);
}
}
if ((i + 1) % 2 == 0) {
bw.write(Integer.toString(left.peek()) + "\n");
} else {
if (left.size() > right.size())
bw.write(Integer.toString(left.peek()) + "\n");
else
bw.write(Integer.toString(right.peek()) + "\n");
}
}
bw.flush();
}
}
Main
๋ณ์)
n : ์ ์์ ๊ฐ์
left : ๋ด๋ฆผ์ฐจ์ ์ฐ์ ์์ ํ
right : ์ค๋ฆ์ฐจ์ ์ฐ์ ์์ ํ
num : ์ธ์น๋ ์ ์
- ์ธ์น๋ ์ ์์ ๊ฐ์(n) ์ ๋ ฅ
- ์ ์์ ๊ฐ์๋งํผ ๋ฐ๋ณตํ์ฌ ์ธ์น๋ ์ ์(num) ์ ๋ ฅ
1) left ์ฐ์ ์์ ํ๊ฐ ๋น์ด์๋ค๋ฉด left ์ฐ์ ์์ ํ์ num ์ถ๊ฐ
2) right ์ฐ์ ์์ ํ์ ๊ฐ์ด ์์ผ๋ฉด์ ๋งจ ์์ ์๋ ๊ฐ๋ณด๋ค ์๊ฑฐ๋ left ์ฐ์ ์์ ํ์ ๋งจ ์์ ์๋ ๊ฐ๋ณด๋ค ์์ผ๋ฉด left ์ฐ์ ์์ ํ์ num ์ถ๊ฐ
3) 2)์ ํด๋นํ๋ ๊ฒฝ์ฐ๊ฐ ์๋๋ผ๋ฉด(= right ์ฐ์ ์์ ํ์ ๋งจ ์์ ์๋ ๊ฐ๋ณด๋ค ํฌ๋ฉด) right ์ฐ์ ์์ ํ์ num ์ถ๊ฐ
4) ์ค๊ฐ ๊ฐ์ ์ฐพ๋ ๊ฒ์ด๋ฏ๋ก left ์ฐ์ ์์ ํ์ right ์ฐ์ ์์ ํ์ size๋ฅผ ๋ณด๊ณ size๊ฐ ๊ฐ๊ฑฐ๋ 1 ์ฐจ์ด ๋๋๋ก ์์
5) ๊ฒฐ๊ณผ ์ถ๋ ฅ
: ํ์ฌ๊น์ง ์ ์๋ฅผ ์ง์๊ฐ ์ธ์ณค๋ค๋ฉด ๋ ์ ์ค์์ ์์ ์๋ฅผ ๋งํด์ผ ํ๋ฏ๋ก left ์ฐ์ ์์ ํ์ ๋งจ ์์ ์๋ ๊ฐ์ ์ถ๋ ฅ
: ํ์ฌ๊น์ง ์ ์๋ฅผ ํ์๊ฐ ์ธ์ณค๋ค๋ฉด left์ right ์ฐ์ ์์ ํ ์ค์์ size๊ฐ ํฐ ์ฐ์ ์์ ํ์ ๋งจ ์์ ์๋ ๊ฐ์ ์ถ๋ ฅ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 17612_์ผํ๋ชฐ (0) | 2023.07.20 |
---|---|
[Baekjoon] 2696_์ค์๊ฐ ๊ตฌํ๊ธฐ (0) | 2023.07.19 |
[Baekjoon] 14235_ํฌ๋ฆฌ์ค๋ง์ค ์ ๋ฌผ (0) | 2023.07.19 |
[Baekjoon] 23757_์์ด๋ค๊ณผ ์ ๋ฌผ ์์ (0) | 2023.07.18 |
[Baekjoon] 19638_์ผํฐ์ ๋ง๋ฒ์ ๋ฟ ๋ง์น (0) | 2023.07.17 |