백준 1021 문제 풀이

문제 링크: https://www.acmicpc.net/problem/1021

사용 자료구조: 데크, 링크드리스트

양쪽에서 데이터를 추가하고 삭제할 수 있어야 했기 때문에 데크를 사용하였다. 하지만 자바 콜랙션의 deque는 사용하지 않고 링크드리스트로 데크를 사용했다. 왜냐하면 target 숫자의 인덱스를 구해야하는데 자바 콜랙션의 deque는 indexOf()메소드를 지원하지 않기 때문이다. 따라서 indexOf()가 있는 링크드리스트를 사용하였다.

찾아낸 규칙

더 적은 방향이동을 결정하기 위해 큐의 중앙을 표현하는 중간 인덱스를 사용하자!
중간 인덱스를 찾을때 홀수 짝수와 상관없이 (데크.size()-1)/2를 해주면 된다.
뽑아야할 숫자의 인덱스를 찾고 중간 인덱스와 비교한다. 중간보다 숫자의 인덱스가 작거나 같으면 왼쪽으로 이동, 크면 오른쪽으로 이동한다. 이동할때마다 숫자를 세어준다. 이동을 마치면 데크에서 빼낸다.

코드 설명

1~n을 담을 데크를 LinkedList로 선언하고 숫자를 담아준다. 뽑을 숫자도 배열을 만들어 순서대로 담아준다.
타깃 숫자들을 순서대로 거쳐가며 데크에서 타깃 수의 인덱스와 중간 인덱스를 비교한다.
만약 중간 인덱스와 같거나 더 작으면 중간인덱스 보다 타깃이 앞쪽에 있으므로 왼쪽으로 큐를 밀고, 더 크면 중간 인덱스보다 타깃이 뒷쪽에 있으므로 오른쪽으로 큐를 민다.
큐를 밀때마다 횟수를 세어준다.
큐를 미는 행위는 데크의 맨앞(peek())과 타깃 수가 같을때까지 반복한다. 타깃이 맨앞에 왔으면 pollFirst()하여 꺼내준다.

import java.util.LinkedList;
import java.util.Scanner;
public class Main {
    public void solution(){
        Scanner sc = new Scanner(System.in);
        int n, m;
        int result = 0;
        n = sc.nextInt();
        m = sc.nextInt();

        // 일단 링크드리스트에 1~n까지 다 담기
        LinkedList<Integer> q = new LinkedList<>();
        for(int i = 1; i<=n; i++){
            q.add(i);
        }
        // 뽑을 숫자 순서대로 targets에 담기
        int[] targets = new int[m];
        for(int i = 0; i<m; i++){
            targets[i] = sc.nextInt();
        }

        for(int i = 0; i<m; i++){
            int target = targets[i];
            int cIdx ;

            if(q.indexOf(target) <= (q.size()-1) / 2){ // 중간과 같거나 중간보다 왼쪽에 있으면 왼쪽으로 이동한다.
                while(q.peek() != target){
                    q.offerLast(q.pollFirst());
                    result++;
                }
            } else{ // 중간보다 오른쪽에 있으면 오른쪽으로 이동한다.
                while(q.peek() != target){
                    q.offerFirst(q.pollLast());
                    result++;
                }
            }
            q.pollFirst();
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        new Main().solution();
    }
}

시행착오 및 깨달음

중간 인덱스를 만들어서 비교하고 어떤 방향으로 이동할지 정하자는 로직은 빨리 깨우쳤지만
처음에 어떤 자료구조를 사용할지에 대해 고민이 많았다.
이동 연산이 있으니까 dequeue를 사용하려고

Deque<Integer> q = new ArrayDeque<>()

를 선언했는데 인덱스를 찾는 메소드가 없어서 사용할 수가 없었다. 그래서 클론을 두번 해놓고 왼쪽으로 이동한 횟수와 오른쪽으로 이동한 횟수를 세어서 결정할까 하다가 너무 연산량도 많고 비효율적인거 같아서 관뒀다...ㅎ
그러다가 indexOf() 메소드가 있는 LinkedList로 데크를 사용하기로 하였다.

또한 왼쪽으로 이동할때 조건이 q.indexOf(target) <= (q.size()-1) / 2 인데 타깃의 인덱스가 중간과 같거나 작으면 왼쪽이동이다. 처음에 조건에 '='를 안붙였다가 예시 10 10
1 6 3 2 7 9 8 4 10 5 에서 14번이 아니라 18번이 나왔다.
중간 인덱스의 위치에 타깃이 있으면 왼쪽으로 밀때 오른쪽으로 미는 것보다 한번 더 적게 이동하게 된다는 것을 깨닫고 최소를 위해 '='을 추가해 주었다.

왼쪽이동과 오른쪽이동을 함수를 따로 만들어서 호출하는 형식으로 코드를 짰었는데 이를 현재 코드처럼 함수를 따로 만들지 않고 바로 수행하니까 212ms에서 208ms로 수행시간이 빨라졌다!간단한 것은 함수로 분리하지 않는게 시간이 단축되는것 같다고 느꼈다.

조건과 인덱스를 꼼꼼히 따져보고 정해줘야겠다는 생각을 했다. 또한 링크드리스트의 메소드에도 pollFirst(), pollLast() 등 데크에서 사용하는 메소드를 사용할 수 있다는 것을 알게 되었다.