LinkedList 를 통해 구현하였다
전체 범위의 숫자를 LinkedList에 담아두고 뽑아야 하는 숫자를 만나면 삭제하는 방식으로 구현했다
뽑아야 하는 숫자를 int[] 에 담고
int[] 에 들어있는 숫자를 다 뽑을때 까지 while문을 수행한다.
while문에서 list의 맨 앞 숫자를 뽑아서
해당 숫자와 int[] 의 첫번째 숫자와 비교한다.
만약 다른 숫자라면 LinkedList를 오른쪽 혹은 왼쪽으로 옮긴다
1 2 3 4 5 -> 2 3 4 5 1 (왼쪽으로 이동 시)
최단거리로 옮기기 위해 방향을 구하는 방법은
linkedList에서 뽑아야 하는 숫자의 위치와
linkedList의 크기를 2로 나눈 수를 비교하여
더 가까운 방향으로 int[] 안의 수와 만날 때 까지 linkedList를 움직인다.
package com.exam.자료구조;
// 회전하는 큐
// https://www.acmicpc.net/problem/1021
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class B1021 {
static int N,M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int[] index = new int[M];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < M; i++) {
index[i] = Integer.parseInt(st.nextToken());
}
LinkedList<Integer> d = new LinkedList<>();
for (int i = 1; i < N+1; i++) {
d.add(i);
}
int count =0;
int move = 0;
while(true){
if(count>=M) {
break;
}else if(d.getFirst() == index[count]) {
d.removeFirst();
count++;
}else{
int idx = d.indexOf(index[count]);
int size = d.size()/2;
if(idx>size) {
while(true){
if(d.getFirst() == index[count]) break;
else {
// 리스트를 옮기기 위해
// 마지막 숫자를 temp에 저장 후
// 마지막 숫자를 삭제하고
// (저장해둔 숫자)temp를 첫번째에 삽입한다
int temp = d.getLast();
d.removeLast();
d.addFirst(temp);
move++;
}
}
}else{
while(true) {
if(d.getFirst() == index[count]) break;
else {
// 리스트를 옮기기 위해
// 첫번째 숫자를 temp에 저장 후
// 첫번째 숫자를 삭제하고
// (저장해둔 숫자)temp를 마지막에 삽입한다
int temp = d.getFirst();
d.removeFirst();
d.addLast(temp);
move++;
}
}
}
}
}
System.out.println(move);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 1874 - 스택 수열 (0) | 2022.09.04 |
---|---|
[백준 java] 10866 - 덱 (0) | 2022.09.04 |
[백준 java] 3425 - 고스텍 (0) | 2022.09.02 |
[백준 java] 1654 - 랜선자르기 (0) | 2022.08.30 |
[백준 java] 7662 - 이중 우선순위 큐 (0) | 2022.08.29 |