[BOJ] 18115 - 카드 놓기

1. 문제 해석

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

18115번: 카드 놓기

• 카드를 놓는 방법이 3가지 있다.
• N개의 카드를 다 놓은 후의 결과는 항상 내림 차순이다.
• N개의 카드 놓는 방법이 주어질 때 처음 카드 순서를 구해야 한다.

 

2. 접근방법

• 입력받은 카드 놓기 기술을 이용하여 현재 카드 num의 원래 카드 위치를 찾아 배열 cardOrder에 저장한다.
• 기술 1번, 2번, 3번에 각각 대응하는 배열 인덱스 idx1, idx2, idx3을 선언한다.
• 기술 1번일 경우 cardOrder[idx1]에 num을 저장한다. cardOrder[idx1 + 1] == 0 이면 idx1 +=1로 아니면 idx1 = idx2 + 1로 갱신한다.
• 기술 2번일 경우 cardOrder[idx1] == 0이면 idx2 = idx2 + 1로 아니면 idx2 += 1로 갱신한 후 cardOrder[idx2]에 num을 저장한다.
• 기술 3번일 경우 현재 가지고 있는 카드 중에서 제일 마지막에 위치한 카드 이기 때문에 cardOrder[idx3]에 num을 저장하고 idx3 -= 1로 갱신한다.

 

3. 주의할 점

• N이 최대 10^6이기 때문에 시간 제한에 주의해야 한다.

 

4. 소스코드

 

#include <iostream>

using namespace std;

int N;
int a[1000001];
int cardOrder[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];

	int num = N;
	int idx1 = 0, idx2 = 1, idx3 = N - 1;
	for (int i = 0; i < N; i++) {
		if (a[i] == 1) {
			cardOrder[idx1] = num;
			if (cardOrder[idx1 + 1] == 0) idx1++;
			else idx1 = idx2 + 1;
		}
		else if (a[i] == 2) {
			if (cardOrder[idx1 + 1] == 0) idx2 = idx1 + 1;
			else idx2 += 1;
			cardOrder[idx2] = num;
		}
		else {
			cardOrder[idx3] = num;
			idx3--;
		}
		num--;
	}

	for (int i = 0; i < N; i++) cout << cardOrder[i] << ' ';

	return 0;
}