1835 - 카드(deque) 💭

문제 https://www.acmicpc.net/problem/1835

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다. 마술을 하는 순서는 다음과 같다.

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다. 카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

예제 입력 1 복사

4

예제 출력 1 복사

2 1 4 3

힌트

1. 2 1 4 3에서 2를 가장 뒤로 옮긴다. (1 4 3 2)
2. 1을 책상 위에 옮겨놓는다. (4 3 2)
3. 4 3 2 에서 4, 3을 뒤로 옮긴다. (2 4 3)
4. 2를 책상 위로 옮겨놓는다. (4 3)
5. 4 3 에서 가장 앞에 있는 것을 뒤로 3번 옮긴    다. (3 4)
6. 3을 책상 위로 옮겨놓는다. (4)
7. 4를 책상 위로 옮겨놓는다. (완료)

 

💡 이 문제를 보고 내가 생각한 것들, 생각한 순서

 

💡 어떤 자료구조를 택했고 그 이유는?

 

 💡 그 자료구조를 이용해서 구체적으로 문제를 해결하는 로직 

from collections import deque

N = int(input())
dq = deque()

for i in range(N):
    card = N - i
    dq.appendleft(card)

    for _ in range(card):
        popCard = dq.pop()
        dq.appendleft(popCard)

print(*dq)

from collections import deque

N = int(input())
dq = deque() # 덱을사용

for i in range(N): 
    card = N - i # N-i 번만큼을 카드에 넣음
    dq.appendleft(card) #덱의 맨앞에 넣는다.1을 맨앞으로 이동

    for _ in range(card): # N-i번 반복
        popCard = dq.pop() # 맨마지막것을 뽑아서,popCard에 넣는다.
        dq.appendleft(popCard) #dq맨앞에 뽑은popCard를 넣는다.

print(*dq)

https://omins.tistory.com/36

 

💡 중요한점

*을 넣으면 공백기준으로 표기해줌, *안넣으면 날것으로 나옴