์ง๋ฏผ์ด๋ N๊ฐ์ ์์๋ฅผ ํฌํจํ๊ณ ์๋ ์๋ฐฉํฅ ์ํ ํ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ์ง๋ฏผ์ด๋ ์ด ํ์์ ๋ช ๊ฐ์ ์์๋ฅผ ๋ฝ์๋ด๋ ค๊ณ ํ๋ค.
์ง๋ฏผ์ด๋ ์ด ํ์์ ๋ค์๊ณผ ๊ฐ์ 3๊ฐ์ง ์ฐ์ฐ์ ์ํํ ์ ์๋ค.
์ฒซ ๋ฒ์งธ ์์๋ฅผ ๋ฝ์๋ธ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, ์๋ ํ์ ์์๊ฐ a1, ..., ak์ด์๋ ๊ฒ์ด a2, ..., ak์ ๊ฐ์ด ๋๋ค.
์ผ์ชฝ์ผ๋ก ํ ์นธ ์ด๋์ํจ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, a1, ..., ak๊ฐ a2, ..., ak, a1์ด ๋๋ค.
์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋์ํจ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, a1, ..., ak๊ฐ ak, a1, ..., ak-1์ด ๋๋ค.
ํ์ ์ฒ์์ ํฌํจ๋์ด ์๋ ์ N์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ง๋ฏผ์ด๊ฐ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์์ ์์น๊ฐ ์ฃผ์ด์ง๋ค. (์ด ์์น๋ ๊ฐ์ฅ ์ฒ์ ํ์์์ ์์น์ด๋ค.) ์ด๋, ๊ทธ ์์๋ฅผ ์ฃผ์ด์ง ์์๋๋ก ๋ฝ์๋ด๋๋ฐ ๋๋ 2๋ฒ, 3๋ฒ ์ฐ์ฐ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ์ ํฌ๊ธฐ N๊ณผ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. N์ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๊ณ , M์ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค์๋ ์ง๋ฏผ์ด๊ฐ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ์์น๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์์น๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌธ์ ์ ์ ๋ต์ ์ถ๋ ฅํ๋ค.
๐ก list ์ฌ์ฉ
๐ก target๊ณผ ๊ฐ์ผ๋ฉด removeํ์ฌ list์์ ๋นผ์ค
๐ก ์ ์ฒด ์ฌ์ด์ฆ์ ์ธ๋ฑ์ค ๊ฐ์ ๋น๊ตํด์ ์ธ๋ฑ์ค๊ฐ์ด ์ ์ฒด ์ฌ์ด์ฆ์์ ๋ฐ๋ณด๋ค ํฌ๋ฉด ์ค๋ฅธ์ชฝ ํ ์นธ ์ด๋, ๋ฐ๋๋ฉด ์ผ์ชฝ ํ ์นธ ์ด๋
ArrayList<Integer> list = new ArrayList<>();
if(list.get(0) == target[idx]) {
list.remove(0);
idx++;
}
else {
int len = list.size();
int index = list.indexOf(target[idx]);
if(index > len/2) {
for(int i=len-1; i>=index; i--) {
int tmp = list.remove(list.size()-1);
list.add(0, tmp);
sum++;
}
} else {
for(int i=0; i<index; i++) {
int tmp = list.remove(0);
list.add(len-1, tmp);
sum++;
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class BOJ_1021 {
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 m = Integer.parseInt(s[1]);
int[] target = new int[m];
s = br.readLine().split(" ");
for(int i=0; i<m; i++) {
target[i] = Integer.parseInt(s[i]);
}
ArrayList<Integer> list = new ArrayList<>();
for(int i=1; i<=n; i++) {
list.add(i);
}
int sum = 0;
int idx = 0;
while(list.size() != 0) {
if(idx >= m) break;
if(list.get(0) == target[idx]) {
list.remove(0);
idx++;
} else {
int len = list.size();
int index = list.indexOf(target[idx]);
if(index > len/2) {
for(int i=len-1; i>=index; i--) {
int tmp = list.remove(list.size()-1);
list.add(0, tmp);
sum++;
}
} else {
for(int i=0; i<index; i++) {
int tmp = list.remove(0);
list.add(len-1, tmp);
sum++;
}
}
}
}
System.out.println(sum);
}
}
์ฑ๊ณตโจ