18115 카드 놓기

기술에 따라 카드를 뽑았을 때

우연히도 1,2, ..., N 이 나왔다

원래의 카드가 어떻게 쌓여있었는지 찾는 문제

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

1. 문제

---

간단 설명

랜덤하게 섞인 카드 패를 들고있는 상태

다음 세가지 기술을 쓸 수 있음

1. 제일 위에서 카드 한장 뽑기

2. 위에서 두번째 카드 뽑기 (2장 이상일때만 가능)

3. 제일 밑에 있는 카드 뽑기 (2장 이상일떄만 가능)

이렇게 뽑았는데 1,2,...,N이 나왔을 때

원래의 패를 구하는 문제

2. 문제 분석

---

카드 5개에 스킬 2 3 3 2 1 를 예시로 들면

초기 상태. 어떤 순서인지 알 수 없음.

위에서 부터 X1, X2, … , X5로 놓음

1. 2번 스킬 사용

위에서 두번째인 X2가 뽑힘

1. 3번 스킬 사용

X5가 뽑힘

1. 3번 스킬 두번째 사용

X4가 뽑힘

1. 2번 스킬 두번째 사용

X3이 뽑힘

1. 마지막 1번 스킬 사용

X1이 뽑히면 이런 순서로 카드가 뽑힌 상태

이렇게 뽑은 순서가 위에서 부터 1,2,3,4,5 이므로

X1 = 1, X3= 2, X4 = 3, X5 = 4, X2= 5이다

X를 순서대로 정렬하면 처음 카드를 구할 수 있음

1 5 2 3 4

뽑은 카드를 아래서부터 위로 쌓아야하는 부분이 햇갈려서 문제를 이해하는데 시간이 좀 걸렸다

---

풀이는 덱을 이용하면 간단히 해결 가능

각 스킬의 역함수를 구해서 반대로 수행해주면 끝

2 3 3 2 1로 수행했다면, 1,2,3,4,5 카드를 반대로 1 2 3 3 2로 수행하면 원래 카드가 구해진다

각 스킬의 역함수는

• 첫번째 스킬 제일 위의 카드를 뽑기는 뽑아놓은 카드의 제일 위의 카드를 뽑아 덱의 앞에 넣기

• 두번째 스킬 위에서 두번째 카드를 뽑기는 뽑아놓은 카드를 덱의 앞에서 두번째에 넣기

• 세번째 스킬 제일 밑에 있는 카드를 뽑기는 뽑아놓은 카드를 덱의 제일 뒤에 넣기

를 수행해주면 된다

필요변수

카드 개수 N,

스킬 순서를 저장할 벡터 또는 덱

카드 순서를 저장할 덱

그 외 임시 변수들

알고리즘

1. 카드 개수 입력받고 스킬 순서를 저장
2. 스킬 순서를 역으로 뒤집는다 
3. 스킬 개수만큼 각 스킬에 대해 역함수를 수행한다
    3-1. 스킬 1이라면 덱의 맨 앞에 카드 넣기
    3-2. 스킬 2이라면 덱의 두번째에 카드 넣기
    3-3. 스킬 3이라면 덱의 맨 뒤에 카드 넣기

3. 소스코드

---

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N;	cin >> N;
	deque<int> order;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		order.push_back(tmp);
	}

	reverse(order.begin(), order.end());

	deque<int> origin;

	int card = 1;
	for(int i=0; i<N; i++){

		if (order[i] == 1) {
			origin.push_front(card);
			card++;
		}
		else if (order[i] == 2) {
			// 두번째에 카드 넣기
            // 첫번째 원소를 빼서 들고있다가 두번째꺼 넣고 첫번째를 넣음
			int tmp = origin.front();
			origin.pop_front();
			origin.push_front(card);
			origin.push_front(tmp);
			card++;
		}
		else if (order[i] == 3) {
			origin.push_back(card);
			card++;
		}
	}

	for (auto it : origin) {
		cout << it << " ";
	}

	return 0;
}

import sys
from collections import deque # 콜렉션의 덱 사용

n = int(input())
num_list = list(map(int, input().split()))
num_list.reverse()

dq=deque()

for i in range(n):
   if num_list[i] == 1:
      dq.appendleft(i+1)
   elif num_list[i] == 2:
      dq.insert(1, i+1) # 두번째에 넣기
   elif num_list[i] ==3:
      dq.append(i+1)

for i in dq:
   print(i, end=" ")