[Algorithm] ๐Ÿ”Œ๋ฐฑ์ค€ 1700 ๋ฉ€ํ‹ฐํƒญ ์Šค์ผ€์ค„๋ง

0. ๋ฌธ์ œ

๊ธฐ์ˆ™์‚ฌ์—์„œ ์‚ด๊ณ  ์žˆ๋Š” ์ค€๊ทœ๋Š” ํ•œ ๊ฐœ์˜ ๋ฉ€ํ‹ฐํƒญ์„ ์ด์šฉํ•˜๊ณ  ์žˆ๋‹ค. ์ค€๊ทœ๋Š” ํ‚ค๋ณด๋“œ, ํ—ค์–ด๋“œ๋ผ์ด๊ธฐ, ํ•ธ๋“œํฐ ์ถฉ์ „๊ธฐ, ๋””์ง€ํ„ธ ์นด๋ฉ”๋ผ ์ถฉ์ „๊ธฐ ๋“ฑ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์ „๊ธฐ์šฉํ’ˆ์„ ์‚ฌ์šฉํ•˜๋ฉด์„œ ์–ด์ฉ” ์ˆ˜ ์—†์ด ๊ฐ์ข… ์ „๊ธฐ์šฉํ’ˆ์˜ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ๋บ๋‹ค ๊ฝ‚์•˜๋‹ค ํ•˜๋Š” ๋ถˆํŽธํ•จ์„ ๊ฒช๊ณ  ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ค€๊ทœ๋Š” ์ž์‹ ์˜ ์ƒํ™œ ํŒจํ„ด์„ ๋ถ„์„ํ•˜์—ฌ, ์ž๊ธฐ๊ฐ€ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ๋Š” ์ „๊ธฐ์šฉํ’ˆ์˜ ์‚ฌ์šฉ์ˆœ์„œ๋ฅผ ์•Œ์•„๋‚ด์—ˆ๊ณ , ์ด๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ๋นผ๋Š” ํšŸ์ˆ˜๋ฅผ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๊ณ ์•ˆํ•˜์—ฌ ๋ณด๋‹ค ์พŒ์ ํ•œ ์ƒํ™œํ™˜๊ฒฝ์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด 3 ๊ตฌ(๊ตฌ๋ฉ์ด ์„ธ ๊ฐœ ๋‹ฌ๋ฆฐ) ๋ฉ€ํ‹ฐํƒญ์„ ์“ธ ๋•Œ, ์ „๊ธฐ์šฉํ’ˆ์˜ ์‚ฌ์šฉ ์ˆœ์„œ๊ฐ€ ์•„๋ž˜์™€ ๊ฐ™์ด ์ฃผ์–ด์ง„๋‹ค๋ฉด,

1. ํ‚ค๋ณด๋“œ
2. ํ—ค์–ด๋“œ๋ผ์ด๊ธฐ
3. ํ•ธ๋“œํฐ ์ถฉ์ „๊ธฐ
4. ๋””์ง€ํ„ธ ์นด๋ฉ”๋ผ ์ถฉ์ „๊ธฐ
5. ํ‚ค๋ณด๋“œ
6. ํ—ค์–ด๋“œ๋ผ์ด๊ธฐ

ํ‚ค๋ณด๋“œ, ํ—ค์–ด๋“œ๋ผ์ด๊ธฐ, ํ•ธ๋“œํฐ ์ถฉ์ „๊ธฐ์˜ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ๋ฉ€ํ‹ฐํƒญ์— ๊ฝ‚์€ ๋‹ค์Œ ๋””์ง€ํ„ธ ์นด๋ฉ”๋ผ ์ถฉ์ „๊ธฐ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ๊ฝ‚๊ธฐ ์ „์— ํ•ธ๋“œํฐ์ถฉ์ „๊ธฐ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ๋นผ๋Š” ๊ฒƒ์ด ์ตœ์ ์ผ ๊ฒƒ์ด๋ฏ€๋กœ ํ”Œ๋Ÿฌ๊ทธ๋Š” ํ•œ ๋ฒˆ๋งŒ ๋นผ๋ฉด ๋œ๋‹ค.

์ž…๋ ฅ
์ฒซ ์ค„์—๋Š” ๋ฉ€ํ‹ฐํƒญ ๊ตฌ๋ฉ์˜ ๊ฐœ์ˆ˜ N (1 โ‰ค N โ‰ค 100)๊ณผ ์ „๊ธฐ ์šฉํ’ˆ์˜ ์ด ์‚ฌ์šฉํšŸ์ˆ˜ K (1 โ‰ค K โ‰ค 100)๊ฐ€ ์ •์ˆ˜๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋‘ ๋ฒˆ์งธ ์ค„์—๋Š” ์ „๊ธฐ์šฉํ’ˆ์˜ ์ด๋ฆ„์ด K ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ์‚ฌ์šฉ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ค„์˜ ๋ชจ๋“  ์ •์ˆ˜ ์‚ฌ์ด๋Š” ๊ณต๋ฐฑ๋ฌธ์ž๋กœ ๊ตฌ๋ถ„๋˜์–ด ์žˆ๋‹ค.

์ถœ๋ ฅ
ํ•˜๋‚˜์”ฉ ํ”Œ๋Ÿฌ๊ทธ๋ฅผ ๋นผ๋Š” ์ตœ์†Œ์˜ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜์‹œ์˜ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ๋ฉ€ํ‹ฐํƒญ ๋น„์–ด์žˆ์œผ๋ฉด ๊ฝ‚๊ธฐ
๐Ÿ’ก ์ด๋ฏธ ๊ฝ‚ํ˜€์žˆ์œผ๋ฉด ๋„˜๊ธฐ๊ธฐ
๐Ÿ’ก ๋ฉ€ํ‹ฐํƒญ ๋ชจ๋‘ ์‚ฌ์šฉ์ค‘์ด๋ฉด, ์•ž์œผ๋กœ ์•ˆ ์“ฐ์ผ ์ „๊ธฐ๊ธฐ๊ตฌ ๋ฝ‘๊ธฐ
๐Ÿ’ก ์•ž์œผ๋กœ๋„ ๋ชจ๋‘ ์“ด ๋‹ค๋ฉด, ์ œ์ผ ๋‚˜์ค‘์— ์‚ฌ์šฉํ•  ์ „๊ธฐ๊ธฐ๊ตฌ ๋ฝ‘๊ธฐ

2. ํ•ต์‹ฌ ํ’€์ด

1) ๋ฉ€ํ‹ฐํƒญ ๋น„์–ด์žˆ์œผ๋ฉด ๊ฝ‚๊ธฐ

list.add(now);

2) ์ด๋ฏธ ๊ฝ‚ํ˜€์žˆ์œผ๋ฉด ๋„˜๊ธฐ๊ธฐ

if (list.contains(now)) {
	continue;
}

3) ๋ฉ€ํ‹ฐํƒญ ๋ชจ๋‘ ์‚ฌ์šฉ์ค‘์ด๋ฉด, ์•ž์œผ๋กœ ์•ˆ ์“ฐ์ผ ์ „๊ธฐ๊ธฐ๊ตฌ ๋ฝ‘๊ธฐ
โ†’ ์ฝ˜์„ผํŠธ์™€ ์•ž์œผ๋กœ ๋‚˜์˜ฌ ์ˆ˜ ๋น„๊ตํ•˜์—ฌ, ํ•˜๋‚˜๋ผ๋„ ์ผ์น˜ํ•˜์ง€ ์•Š์œผ๋ฉด ๋” ์ด์ƒ ์—†๋Š” ์ˆ˜๋กœ ์ƒ๊ฐํ•จ

if (!flag) {
	remove = arr;
	break;
}

4) ์•ž์œผ๋กœ๋„ ๋ชจ๋‘ ์“ด ๋‹ค๋ฉด, ์ œ์ผ ๋‚˜์ค‘์— ์‚ฌ์šฉํ•  ์ „๊ธฐ๊ธฐ๊ตฌ ๋ฝ‘๊ธฐ
โ†’ ์ฝ˜์„ผํŠธ์™€ ์•ž์œผ๋กœ ๋‚˜์˜ฌ ์ˆ˜ ๋น„๊ตํ•˜์—ฌ, idx ๊ฐ’ ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ์ฐพ์•„์„œ ์ œ๊ฑฐํ•จ

if (list.size() == n) {
...
for (int arr : list) {
	for (int j = i + 1; j < k; j++) {
		if (arr == elec[j]) {
			if(idx < j) {
				idx = j;
				remove = arr;
			}
...
}

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Greedy_17 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");

		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);

		int[] elec = new int[k];

		s = br.readLine().split(" ");
		for (int i = 0; i < k; i++) {
			elec[i] = Integer.parseInt(s[i]);
		}

		int count = 0;
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < k; i++) {
			int now = elec[i];
			if (list.contains(now)) {
				continue;
			}

			if (list.size() == n) {
				int remove = -1;
				int idx = -1;
				for (int arr : list) {
					boolean flag = false;
					for (int j = i + 1; j < k; j++) {
						if (arr == elec[j]) {
							if(idx < j) {
								idx = j;
								remove = arr;
							}
							flag = true;
							break;
						}
					}

					if (!flag) {
						remove = arr;
						break;
					}
				}

				list.remove(Integer.valueOf(remove));
				count++;
			}
			
			list.add(now);
			
		}

		System.out.println(count);

	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ
์ดํ•ดํ•˜๋Š” ๊ฑฐ๋Š” ์•ˆ ํž˜๋“ค์—ˆ๋Š”๋ฐ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•˜๋Š” ๊ฒŒ ํž˜๋“ค์—ˆ๋‹ค...!

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ