[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. ๊ฒฐ๊ณผ
์ฑ๊ณตโจ
์ดํดํ๋ ๊ฑฐ๋ ์ ํ๋ค์๋๋ฐ ์ฝ๋๋ก ๊ตฌํํ๋ ๊ฒ ํ๋ค์๋ค...!
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๋ฐฑ์ค 1700 ๋ฉํฐํญ ์ค์ผ์ค๋ง), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-1700-๋ฉํฐํญ-์ค์ผ์ค๋ง์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค