[Java] 18115번. 카드 놓기

1. 문제 분석

손에 있는 카드를 특정 행위로 내려놓고 그 카드의 결과와 행위를 알려주고 원래 카드의 순서를 추측하는 문제이다.

 

행할 수 있는 동작은 세가지 이다.

1. 제일 위의 카드 1장을 내려놓는다.

2. 위에서 두번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 사용 가능.

3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 사용 가능.

 

동작이 끝나면 카드가 위에서부터 차례대로 1,2,3,4,5, ..., N으로 정렬된다.

어떤 동작을 했는지 주어지고, 처음 카드의 순서를 계산하면 된다.

 

쉽게 말하면 행했던 행동들을 정반대로 하면 된다.

 

가장 마지막에 했던 행동부터 차례대로 원상복귀 시켜놓으면 된다. 예제를 통해서 보자.

 

예제)

5장의 카드에 차례대로 2,3,3,2,1번 행동을 하였고

결론적으로 카드는 위에서부터 차례대로 1,2,3,4,5가 되었다.

 

그러면 가장 위쪽의 카드인 1은 가장 마지막 행동인 1번 행동에 의해서 들어 온 것이고,

'2' 카드는 뒤에서 2번째 행동인 2번 행동에 의해서 놓인 것이다.

'3' 카드는 3번 행동에 의해서 놓인 것이고,

'4' 카드는 3번 행동에 의해서 놓인 것이고,

'5'카드는 2번 행동에 의해서 놓인 것이다.

 

더 자세하게 말하면,

'1'카드는 남은 카드들 중에서 가장 위에서 왔을 것이므로 가장 위에 올려준다.

'2'카드는 남은 카드들 중, 위에서 두번째에서 왔을 것이므로 위에서 두번째 위치에 넣어준다.

'3'카드는 남은 카드들 중, 가장 아래에서 왔을 것이므로 아래로 넣어준다.

'4'카드는 남은 카드들 중, 가장 아래에서 왔을 것이므로 아래에 넣어준다.

'5'카드는 남은 카드들 중, 위에서 두번째에서 왔을 것이므로 위에서 두번째 위치에 넣어준다.

 

 

따라서, 원래의 카드 정렬은 1,5,2,3,4 이다.

 

여기서 POINT!

위쪽과 아래쪽 양쪽에서 삽입이 되는 형태이기 때문에 Deque를 사용해서 구현하면 된다.

 

❗중요❗

이 예제를 통해서 우리는 다음과 같은 사실들을 알 수 있다.

(1) 카드는 1번카드부터 N번 카드까지 차례대로 복귀된다.

(2) 가장 뒤 명령어부터 차례대로 분석한다.

(3) 1번 명령어를 복귀하려면 위로 추가한다.

(4) 2번 명령어를 복귀하려면 위에서 두번째로 추가한다.

(5) 3번 명령어를 복귀하려면 가장 아래에 추가한다.

*참고로 Deque에서 위쪽이 앞이고, 아래쪽이 뒤이다.

2. 구현

사용할 주요 변수

deque : 원래 카드의 정렬을 의미한다.

 

해결 과정

(1) for문을 1부터 n까지 실행하여 아래 과정들을 반복한다.

(2) i가 1일 때, n-1번째 인덱스의 명령어를 식별한다.

(3) 명령어가 1이면 deque의 가장 앞에 i를 추가한다.

(4) 명령어가 2이면 deque의 가장 앞에 요소를 빼고, i를 추가한 후 가장 앞에 있던 요소를 다시 추가한다.

     * deque는 맨 앞 또는 맨 뒤가 아니면 원칙적으로 접근이 불가능하기 때문이다.

(5) 명령어가 3이면 deque의 가장 뒤에 i를 추가한다.

 

3. 최종코드

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

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));

        int n = Integer.parseInt(br.readLine());

        Deque<Integer> deque = new ArrayDeque<>();

        String str = br.readLine();
        String[] command = str.split(" ");
        for(int i=1; i<=n; i++){
            switch(command[n-i]){
                case "1":
                    deque.addFirst(i);
                    break;
                case "2":
                    int temp = deque.pollFirst();
                    deque.addFirst(i);
                    deque.addFirst(temp);
                    break;
                case "3":
                    deque.addLast(i);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            sb.append(deque.pollFirst()).append(" ");
        }

        bw.write(sb.toString());

        br.close();
        bw.close();
    }
}