[백준]18115번 카드놓기 - C/C++

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

18115번: 카드 놓기

문제

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

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

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

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

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

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

출력

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

---

카드를 모두 내려놓았을 때 카드가 위부터 1~ N 이므로 첫 번째 내려놓은 카드는 N 그다음 카드는 N-1... 마지막으로 내려놓은 카드가 1이 된다. skill [] 배열에는 다음 스킬을 사용했을 때의 인덱스 값을 저장해둔다. 

 

그리고 위 그림과 같이 포인터들을 옮겨주면서 문제를 풀면 된다. 이때 주의해야 할 점은 1번 스킬을 사용한 후에는 2번 포인터까지 옮겨주는 것과 단순히 1칸만 옮기는 것이 아니라 비어있는 칸까지 포인터를 옮겨야 된다는 것이다. 

#include <iostream>

using namespace std;
int N;
int skill[4];
int ans[1000001] = { 0 };
int arr[1000001] = { 0 };

void change(int i) {
	if (i == 1 || i == 2) {
		do {
			skill[i]++;
		} while (arr[skill[i]]);
	}
	else {
		do {
			skill[i]--;
		} while (arr[skill[i]]);

	}
}
int main() {
	cin >> N;
	skill[1] = 1;
	skill[2] = 2;
	skill[3] = N;
	for (int i = N; i >= 1 ; i--) {
		int type;
		cin >> type;
		arr[skill[type]] = i;
		switch (type) {
		case 1 :
			change(1);
			change(2);
			break;
		case 2:
			change(2);
			break;
		case 3:
			change(3);
			break;
		}
	}
	for (int i = 1; i <= N; i++)
		cout << arr[i] << " ";
	
	return 0;
}

---

처음에는 포인터를 한칸씩만 옮겼더니 틀렸습니다가 나와서 다시 한번 생각해보았다. 이미 차지한 자리는 사용이 불가하므로 그것만 건너뛰어주면 되는 것이었다!