[백준/queue] 1158번 : 요세푸스 문제

- 문제 : https://www.acmicpc.net/problem/1158

 

Silver Lv4 문제이고, 스스로 푼 문제다!

어렵지 않은 문제였지만 문제 이해부터  정답 출력까지 실수를 많이해서 그 과정을 기록 해보려 한다. 

 

1. 문제 이해

처음에는 매번 k번째에 있는 사람을 빼야하는 줄 알았는데, 정답을 보니 이해한 내용은 아래와 같다. 

원 순열에서 k번째 있는 원소를 제거하는데, 제거한 뒤 다음 사람을 뺄 때는 이전 순서에서 남은 사람 중 k번째 사람을 빼는 것이었다. 

이거를 매번 인덱스나 남은 원소를 고려하면서 진행해야 싶었는데 생각해보니 큐로 하면 간단하게 해결되는 문제였다. 

 

2. <1,2,3,5> 출력 

리스트를 출력하면 [1,2,3,4,5] 이런식으로 출력이 되기 때문에 일일히 인덱스 별로 분기문 나눠서 출력해야했다. 

 

3. 시간초과

queue.pop(0)으로 풀었을 때는 4%에서 시간초과가 발생했다. 그래서 queue를 리스트가 아닌 deque()로 변경했더니 무사히 통과했다. 

 

- 정답 풀이 : 

from collections import deque

n, k = map(int, input().split())

answer = ['<']
queue = deque([i for i in range(1, n + 1)])
sequence = 1
while queue:
    x = queue.popleft()
    
    if sequence < k:
        queue.append(x)
        sequence += 1
    elif sequence == k:
        answer.append(x)
        sequence = 1
        
for i in range(n + 1):
    if i == 0:
        print(answer[i], end = '')
    elif i == n:
        print(answer[i], end = '')
    else:
        print(answer[i], end = ', ')
    
print('>')