스택이나 큐로는 어떻게 풀어야 할지 감이 안 잡혀서 나는 첨에 규칙을 찾아서 스택을 간단하기 이용해서 풀었다. 그 후, 구글링으로 큐를 이용해 푸는 방법을 대충 이해하고 내 손으로 코드를 짜봤다.
1. 규칙 이용
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
num = 0
len = N
list = [i+1 for i in range(N)]
print('<', end='')
for _ in range(N):
num += K-1
while num >= len:
num -= len
print(list.pop(num), end='')
len -= 1
if len != 0:
print(', ', end='')
print('>', end='')- 규칙을 찾기 위해 예제 문제를 이용해서 출력되는 요소들의 인덱스를 나열해 보았다.
- 2, 4, 1, 3, 2, 0, 0으로 나열되었고 K-1만큼 더하고 얘가 리스트 길이를 넘느냐에 따라 어떤 숫자를 뺄 거라는 예상을 했다.
- 역시 리스트 길이를 넘으면 리스트 길이만큼 뺀다는 것을 발견했다.
- 이렇게 출력할 인덱스를 찾고 pop해서 출력한다.
2. 큐 이용
import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
queue = deque([i+1 for i in range(N)])
res = []
for _ in range(N):
for _ in range(K-1):
queue.append(queue.popleft())
res.append(queue.popleft())
print('<', end='')
print(*res, sep=', ', end='')
print('>', end='')- 아주 아이디어가 놀라운 문제라고 생각한다. 과연 내가 떠올릴 수 있으까..?
- 나는 큐를 이용해서 원으로 이어진 즉, 처음과 끝이 연결된 걸 표현할 방법을 찾지 못했는데... K-1만큼 앞의 요소를 그냥 맨 뒤로 옮겨버리는 것이다.
- 그런 후 맨 앞에 있는 친구를 팝시켜서 result 리스트에 담는다.
- 결과적으로 res에는 우리가 원하는 순서대로 요소가 담겨 있고 얘를 출력하면 끝
2-1. join을 이용해서 출력
import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
queue = deque([i+1 for i in range(N)])
res = []
for _ in range(N):
for _ in range(K-1):
queue.append(queue.popleft())
res.append(str(queue.popleft()))
print('<' + ', '.join(res) + '>')- 구글링하며 찾은 코드이다. join은 리스트를 문자열로 만드는 함수이므로 먼저 res에 str형식으로 저장한다.
- join을 이용해서 res의 요소들을 , 로 연결해서 문자열로 만든다.
- join의 결과값이 문자열이기에 +도 가능한 것!
결과
- 역시 규칙을 찾은 게 가장 빠르긴 하다.
