๋ฌธ์ (์ถ์ฒ: https://www.acmicpc.net/problem/19640)
< ํ์ฅ์ค์ ๊ท์น >
๋ฌธ์ ํ์ด
์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
์ฐ์ ์์ ํ์๋ [๊ทผ๋ฌด ์ผ์, ํ์ฅ์ค์ด ๊ธํ ์ ๋, ์ค ๋ฒํธ, ์๋ ์์, ๋ฐ์นด ์ฌ๋ถ]๋ฅผ ์ ์ฅํ๋ค.
์ฐ์ ์์๋ ๊ทผ๋ฌด ์ผ์(๋ด๋ฆผ์ฐจ์) > ํ์ฅ์ค์ด ๊ธํ ์ ๋(๋ด๋ฆผ์ฐจ์) > ์ค ๋ฒํธ(์ค๋ฆ์ฐจ์)์ด๋ค.
my solution (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _19640_ { // ํ์ฅ์ค์ ๊ท์น
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) {
if (o1[1] == o2[1]) {
return o1[2] - o2[2];
}
return o2[1] - o1[1];
}
return o2[0] - o1[0];
}
});
int idx = 0;
int check = 0;
ArrayList<int[]> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(bf.readLine());
int d = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
if (i == k)
check = 1;
else
check = 0;
arr.add(new int[] { d, h, idx, i, check });
idx += 1;
if (idx == m)
idx = 0;
}
int result = 0;
for (int i = 0; i < m; i++) {
if (i >= n)
break;
queue.add(arr.get(i));
}
while (true) {
int temp[] = queue.poll();
if (temp[4] == 1)
break;
result += 1;
if (temp[3] + m < n) {
queue.add(arr.get(temp[3] + m));
}
}
System.out.println(result);
}
}
Main
๋ณ์)
n : ์ฌ์์ ์
m : ์๋ก์ด ์ค์ ์
k : ์์ ์ ์์ ์ ์๋ ์ฌ์์ ์
queue : [๊ทผ๋ฌด ์ผ์, ๊ธํ ์ ๋, ์ค ๋ฒํธ, ์๋ ์์, ๋ฐ์นด ์ฌ๋ถ] / ๊ทผ๋ฌด ์ผ์(๋ด๋ฆผ์ฐจ์) > ํ์ฅ์ค์ด ๊ธํ ์ ๋(๋ด๋ฆผ์ฐจ์) > ์ค ๋ฒํธ(์ค๋ฆ์ฐจ์)
idx : ์ค ๋ฒํธ
check : ๋ฐ์นด ์ฌ๋ถ
arr : [๊ทผ๋ฌด ์ผ์, ๊ธํ ์ ๋, ์ค ๋ฒํธ, ์๋ ์์, ๋ฐ์นด ์ฌ๋ถ]
d : ๊ทผ๋ฌด ์ผ์
h : ๊ธํ ์ ๋
result : ๋ฐ์นด๊ฐ ์ด์ฉํ๊ธฐ๊น์ง ๋ช ๋ช ์ด ์ฌ์ฉํ๋์ง ์ถ๋ ฅ
- ์ฌ์์ ์(n), ์๋ก์ด ์ค์ ์(m), ์์ ์ ์์ ์ ์๋ ์ฌ์์ ์(k) ์ ๋ ฅ
- ArrayList์ [๊ทผ๋ฌด ์ผ์, ๊ธํ ์ ๋, ์ค ๋ฒํธ, ์๋ ์์, ๋ฐ์นด ์ฌ๋ถ] ์ ์ฅ
- ์๋ก์ด ์ค ์๋งํผ ์ฒ์์ ์ฌ๋์ ์ฑ์
: ์ง์ํ ์๋ก์ด ์ค์ ์๋ณด๋ค ์ฌ์์ ์๊ฐ ์ ์ ์ ์์ผ๋ฏ๋ก ๋จ์ ์ฌ์์ด ์์ผ๋ฉด ์ข ๋ฃ
- ํ ์ค์ ์ฑ์ ๋ค๋ฉด ์ฌ์์ ํ์ฅ์ค์ ๋ณด๋
: ๋ณด๋ธ ํ ๊ทธ ์ค์ ๋ค์ ์ฌ๋์ queue์ ์ ์ฅ
: ํ์ฅ์ค ๊ฐ ์ฌ๋์ด ๋ฐ์นด๋ผ๋ฉด ์ข ๋ฃ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 21939_๋ฌธ์ ์ถ์ฒ ์์คํ Version 1 (0) | 2023.07.24 |
---|---|
[Baekjoon] 22252_์ ๋ณด ์์ธ ํธ์ (0) | 2023.07.21 |
[Baekjoon] 17612_์ผํ๋ชฐ (0) | 2023.07.20 |
[Baekjoon] 2696_์ค์๊ฐ ๊ตฌํ๊ธฐ (0) | 2023.07.19 |
[Baekjoon] 1655_๊ฐ์ด๋ฐ๋ฅผ ๋งํด์ (0) | 2023.07.19 |