[코드트리] 특정 원소 추출 - 자바(Java)

문제

https://www.codetree.ai/problems/extract-specific-elements?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

수열에서 특정한 원소들을 추출하려 합니다. 이 수열에는 다음과 같은 3가지의 연산을 수행할 수 있습니다.

1. 첫 번째 원소를 뽑아냅니다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak이 됩니다.
2. 오른쪽으로 한 칸 이동시킵니다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 됩니다.

특정한 원소들을 모두 뽑아내려 할 때, 2번과 3번 연산을 최소한 몇 번 수행해야 하는지 알아내는 프로그램을 작성해 보세요.

 

입력 예시

10 3
2 9 5

 

출력 예시

8

 

 

코드

첫 번째 줄에는 수열의 크기 n과 추출하려는 원소의 개수 m이 주어집니다.

두 번째 줄에는 추출하려는 원소의 위치가 순서대로 주어집니다.

• 1 ≤ m ≤ n ≤ 50
• 1 ≤ 원소의 위치 ≤ n

 

첫 번째 줄에 문제의 정답을 출력합니다.

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 수열의 크기
        int m = Integer.parseInt(st.nextToken()); // 추출할 원소 개수

        // 덱 선언
        List<Integer> deque = new LinkedList<>();

        // 1부터 n까지 차례대로 넣기
        for (int i = 1; i <= n; i++) {
            deque.addLast(i);
        }

        int count = 0; // 연산 횟수
        st = new StringTokenizer(br.readLine()); // 추출할 원소 위치
        br.close();

        // m번 반복
        for (int i = 0; i < m; i++) {
            // 추출할 원소의 위치에 해당하는 값
            int target = deque.indexOf(Integer.parseInt(st.nextToken()));
            int mid;

            // 중간 인덱스
            if (deque.size() % 2 == 0) {
                mid = deque.size() / 2 - 1;
            } else {
                mid = deque.size() / 2;
            }

            // target이 중간 mid보다 작거나 같으면
            if (target <= mid) {
                // target까지 앞으로 찾기
                for (int j = 0; j < target; j++) {
                    // 맨 앞에 있는 숫자를 맨 뒤로
                    deque.addLast(deque.removeFirst());
                    count++;
                }
            } else { // target이 mid보다 크면
                // target까지 뒤로 찾기
                for (int j = 0; j < deque.size() - target; j++) {
                    // 맨 뒤에 있는 숫자를 맨 앞으로
                    deque.addFirst(deque.removeLast());
                    count++;
                }
            }

            // 덱에서 꺼내기
            deque.pollFirst();
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}