[백준] 18115번. 카드 놓기(JAVA)

문제

https://www.acmicpc.net/problem/18115

---

풀이(12분)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int num = 1;
		Deque<Integer> dq = new ArrayDeque<>();
		for (int i = N - 1; i >= 0; i--) {
			int command = arr[i];
			if (command == 1) {
				dq.addFirst(num++);
				continue;
			}
			if (command == 3) {
				dq.addLast(num++);
				continue;
			}
			int temp = dq.pollFirst();
			dq.addFirst(num++);
			dq.addFirst(temp);
		}

		StringBuilder sb = new StringBuilder();
		while (!dq.isEmpty()) {
			sb.append(dq.pollFirst()).append(" ");
		}

		System.out.println(sb);
	}
}

---

문제 해결 전략

 

카드 복원 과정 정리

문제의 입력이 2 3 3 2 1이라면,
이는 카드가 완성되어가는 순서를 거꾸로 해석해야 하므로
1 2 3 3 2로 뒤집어 생각한다.

기준:

• ← 방향일수록 위쪽,
• → 방향일수록 아래쪽

초기 상태:

• 나에게는 1, 2, 3, 4, 5의 카드가 순서대로 주어져 있다.

1️⃣ 입력: 1

→ 카드 1을 제일 위에 둔다.
현재 상태: 1

2️⃣ 입력: 2

→ 카드 2를 1 아래에 둔다.
현재 상태: 1 2

3️⃣ 입력: 3

→ 카드 3을 맨 아래(오른쪽 끝) 에 둔다.
현재 상태: 1 2 3

4️⃣ 입력: 3

→ 카드 4를 맨 아래에 둔다.
현재 상태: 1 2 3 4

5️⃣ 입력: 2

→ 카드 5를 제일 위에서 두 번째(1 아래) 에 둔다.
현재 상태: 1 5 2 3 4

 

 

✅ 최종 카드 순서: 1 5 2 3 4