백준 1021 - 자료구조

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Deque<Integer> deq = new ArrayDeque<>();
        String[] s = br.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        for(int i = 1; i <= N; i++){
            deq.addFirst(i);
        }
        int sum = 0;

        int M = Integer.parseInt(s[1]);
        String[] s2 = br.readLine().split(" ");

        Deque<Integer> leftcopy = new ArrayDeque<>(deq);
        Deque<Integer> rightcopy = new ArrayDeque<>(deq);

        for(int i = 0; i < M; i++){
            int target = Integer.parseInt(s2[i]);
            int leftCount = left(leftcopy,target);
            int rightCount = right(rightcopy,target);
            sum += Math.min(leftCount,rightCount);
        }
        System.out.println(sum);
    }
    public static int left(Deque<Integer> deq, int target){
        int cnt = 0;

        while(true){
            int getNum = deq.removeLast();
            if(getNum == target) {
                return cnt;
            }
            deq.addFirst(getNum);
            cnt++;
        }
    }
    public static int right(Deque<Integer> deq, int target){
        int cnt = 0;

        while(true){
            cnt++;
            int getNum = deq.removeFirst();
            if(getNum == target) {
                return cnt;
            }
            deq.addLast(getNum);
        }
    }
}

풀이과정 및 리뷰

(초기 1)

1. 덱을 생성해 1~N까지의 수를 차례로 덱에 삽입

2. target과 값이 일치해 덱에서 제거만 하는 경우를 제외하고 left / right에서 각각 제일 앞 요소를 빼서 제일 뒤에 추가하는 로직임을 감안해 int 타입을 반환하는 left / right 함수를 각각 선언

   → 이때, 앞 뒤에서 target을 꺼낼 수 있는게 아니라 앞에서만 꺼낼 수 있으므로, left 함수에 getNum == target 이라면 횟수를 반환하며 메서드를 종료(즉 cnt 증가 안함)하는 방식으로 1번 방식을 접목함

3. 이때, 초기 덱을 파라미터로 넘겨 int min = Math.min(left(deq,target),right(deq,target)) 식을 사용해서 최소값을 구하려 했음

   → 문제점 : 일단 테케가 제대로 맞지 않아 확인해보니 처음 생성했던 덱을 left연산한 최솟값을 구한 이후 똑같은 덱을 사용해서, 초기 덱 순서가 유지되지 않는 문제가 발생

   (초기 2)

   • 각각의 left / right 메서드에 새로운 덱을 복사해 사용 → 메인메서드 for문의 반복이 돌때마다 완전 초기 덱 순서로 초기화돼서 제대로 된 값이 나오지 않음

   (최종)

   • 메인메서드 자체에 left메서드에 넘겨줄 copy 덱 1과, right메서드에 넘겨줄 copy 덱 2 를 따로 생성해 파라미터로 넘겨주게 되면서 각각의 덱 순서가 유지