๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 19640_ํ™”์žฅ์‹ค์˜ ๊ทœ์น™

๋ฟŒ์•ผ._. 2023. 7. 20. 11:36

Gold IV

๋ฌธ์ œ(์ถœ์ฒ˜: 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์— ์ €์žฅ

: ํ™”์žฅ์‹ค ๊ฐ„ ์‚ฌ๋žŒ์ด ๋ฐ์นด๋ผ๋ฉด ์ข…๋ฃŒ