지민이는 N
개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
큐에 처음에 포함되어 있던 수 N
이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
첫째 줄에 큐의 크기 N
과 뽑아내려고 하는 수의 개수 M
이 주어진다. N
은 50보다 작거나 같은 자연수이고, M
은 N
보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
첫째 줄에 문제의 정답을 출력한다.
10 3
1 2 3
0
10 3
2 9 5
8
32 6
27 16 30 11 6 23
59
10 10
1 6 3 2 7 9 8 4 10 5
14
-문제를 번역한 사람: baekjoon
-문제의 오타를 찾은 사람: dhdh6190
-데이터를 추가한 사람: djm03178
import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
public class Code1021 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] temp=br.readLine().split(" ");
int N=Integer.valueOf(temp[0]);
int M=Integer.valueOf(temp[1]);
String[] dels=br.readLine().split(" ");
br.close();
Deque<Integer> d=new LinkedList<>();
for(int i=0;i<N;i++){
d.add(i);
}//0부터 9까지 저장
int count=0;
Boolean isLoop=true;
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=0;i<M;i++){
int del=Integer.valueOf(dels[i])-1;//먼저 첫번째 인덱스
int right=0;
int left=0;
Deque<Integer> r=new LinkedList<>(d);
Deque<Integer> l=new LinkedList<>(d);
while(isLoop){
if(r.getFirst()==del){
d=r;
count+=right;
}
else if(l.getFirst()==del){
d=l;
count+=left;
}
if(del==d.getFirst()){
//0이랑 0이 같느냐...
d.poll();
isLoop=false;
}
else{
//만약 1 8 4라서 0이랑 1은 다른거니까.. 처음 값이랑
//오른쪽으로 회전할지 왼쪽으로 회전할지 정하자
int temr=r.pollLast();//맨 끝을 제일 앞으로
r.addFirst(temr);
right++;
int teml=l.poll();//맨 처음을 제일 끝으로
l.addLast(teml);
left++;
}
}
isLoop=true;
}
bw.write(String.valueOf(count));
bw.write("\n");
bw.flush();
bw.close();
}
}
첫번째의 원소만 뽑을 수 있다고 하였다.
그러므로 왼쪽으로 회전하던지 오른쪽으로 회전하던지 해야한다.
왼쪽으로 회전하는게 효율적일지, 오른쪽으로 회전하는게 효율적일지를 구해야 했다.
그래서 각각의 임시 덱
을 만들고, while문 마다 회전하면서 만약 먼저 같아지면 그 카운트 수만큼 count가 오르고, 그 덱을 d
로 주면 된다.