[백준, BOJ 18115] 카드 놓기(java)

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

18115번: 카드 놓기

---

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ $10^6$)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. $A_i$가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. $A_i$는 1, 2, 3 중 하나이며, $A_n$은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

728x90

 

예제 입력 1

5
1 1 1 1 1

예제 출력 1

5 4 3 2 1

 

예제 입력 2

5
2 3 3 2 1

예제 출력 2

1 5 2 3 4

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;



public class Main {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// n과 수열 A 입력, result 배열 초기화
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] result = new int[n];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int card1 = 0, card2 = 1, card3 = n - 1;
		for(int i = 0, j = n; i < n; i++, j--) {
			if(arr[i] == 1) {
				result[card1] = j;
				card2++;
				card1 = card2 - 1;
			}
			else if(arr[i] == 2) {
				result[card2++] = j;
			}
			else {
				result[card3--] = j;
			}
		}
		
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(result[i] + " ");
		}
		System.out.println(sb);
	}

}