[백준] 1021번

 

이번 문제는 저번에 자료구조를 공부하고 정리해서 글을 쓴 것을 응용하여 백준 문제에 도전했다.

 

처음에 문제를 제대로 이해하지 못해서 삽질을 오래했다.

삽질내용 : 최대한 효율적으로 하기 위해 빠르게 찾는게 목적이다, 하고 이건 덱에 관한 문제니까 앞 뒤로 삭제가 가능하니 앞, 뒤에서 바로바로 삭제하고 값을 빨리 찾아야지 ! 하고 했다가 예제 출력보다 낮게 나와서 일일히 찍어보느라 오래걸렸다.

앞 뒤로 삭제하는게 아닌 그냥 앞에서만, removeFirst() 메소드만 사용하는 것이였다...

 

다시 돌아와서 처음에 짠 코드보다 약 2배가량 줄이는 리팩토링을 거쳤다.

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b1021 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int count = 0; // 2,3 번 연산의 횟수
        int dSize = 0; // 길이의 가운데 값
        //n세팅
        LinkedList<Integer> deque = new LinkedList<Integer>();
        for(int i =1 ; i<n+1; i++){
            deque.add(i);
        }
        //m 세팅
        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[m];

        //m 세팅과 동시에 연산
        for(int i =0; i<m; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if(deque.size() % 2==0){ // 가운데 값이 짝수일 경우를 방지
                dSize = deque.size() / 2 -1;
            } else{
                dSize = deque.size() / 2;
            }

            //실제 연산부분
            while (deque.getFirst() != arr[i]){
                if(deque.indexOf(arr[i])<=dSize) { //앞을 제거해서 뒤에 추가
                    int tmp = Integer.parseInt(String.valueOf(deque.removeFirst()));
                    deque.addLast(tmp);
                    count++;
                } else { //뒤를 제거해서 앞에 추가
                    int tmp = Integer.parseInt(String.valueOf(deque.removeLast()));
                    deque.addFirst(tmp);
                    count++;
                }
            }
            deque.removeFirst();
        }
        System.out.println(count);
    }
}

 

 

나름 재밌었다!