처음 문제를 읽었을 때, 덱 자료 구조를 이해하고 있으면 쉽게 풀 수 있을거라고 생각했지만, "2번과 3번 행동의 최솟값을 출력" 하라는 문구를 보고 정확한 구현 코드가 생각나지 않았다.
최소한의 경우의 수를 뽑아내기 위해 다른 알고리즘을 써야하는건가? 내가 문제를 잘못 이해한건가? 이런 생각들로 인해 30분 이상을 흘려보냈다. 확실히 아직 내가 이해한 상황을 코드로 구현하는데 미숙한 점이 많은 것 같다.
우선, 로직부터 정리하였다.
1. 찾는 값과 덱 안의 요소를 비교 후 이동시켜 첫번째 위치로 오게한다.(2번과 3번 행동)
2. 해당 요소를 뽑는다.(1번 행동)
처음에는 왼쪽과 오른쪽으로 가는 경우의 수를 모두 확인해본 뒤 두 값을 비교하여 상대적으로 더 작은 값을 출력하면 되겠다고 생각했었다. 하지만 코드를 짜던 중 하나의 덱으로 넣어놓은 값을 수정해버리면 두번째 순서의 로직을 수행할 때, 오류가 나게되는 문제가 발생하였다.
clone() 도 생각했지만, 방향성이 잘못되었다고 판단하였으며 왼쪽으로 갈지 오른쪽으로 갈지 정할 기준을 정하면 되겠다고 생각했다. 그리하여 중간값을 기준으로 중간 값의 위치보다 찾을 값의 위치가 작으면 오른쪽(정방향) 크면 왼쪽(역방향)으로 가면 되겠다고 생각했다.
하지만, 60분이 초과되어 결국 다른 사용자의 풀이를 참고하게 되었다.
평소 자주 참고하는 분의 블로그 포스팅이다. 정리가 매우 잘되어 있으니 다른 분들도 참고하면 좋을 듯 하다.
중간값을 기준으로 2번 또는 3번을 택해야 한다는 부분까지는 방향성이 맞긴 했지만, 실제 코드로까진 구현하지 못한것이 아쉬웠다.
아래에 포스팅 글을 참고 및 구현한 로직이다.
😀 성공
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList<Integer> deq = new LinkedList<>();
int count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
for(int i=1; i <= N; i++){
deq.offer(i);
}
int[] seq = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i < M; i++){
seq[i] = Integer.parseInt(st.nextToken());
}
br.close();
for(int i = 0; i < M; i++){
int target_idx = deq.indexOf(seq[i]); // 해당 요소의 인덱스
int half_idx;
if(deq.size()%2 == 0){ // 요소 갯수가 짝수인 경우, 중간지점을 절반 크기의 -1값으로 지정
half_idx = deq.size()/2 -1;
}else{
half_idx = deq.size()/2;
}
if(target_idx <= half_idx){
for(int j=0; j < target_idx; j++){
deq.offerLast(deq.pollFirst());
count++;
}
}else{
for(int j=0; j < deq.size() - target_idx; j++){
deq.offerFirst(deq.pollLast());
count++;
}
}
deq.pollFirst();
}
System.out.println(count);
}
}위에 코드에서 남은 덱의 요소의 갯수가 짝수인 경우, -1값을 중간값으로 지정해주고, 이를 작거나 같은 경우, 왼쪽으로 순환하지 않도록 조건문으로 제한해줌으로써 count 값이 알고리즘에 맞게 카운팅 되도록 구현하였다.
