백준-1158 요세푸스 문제

💡문제 분석 요약
1. Queue 사용(deque)
2. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
3. N은 전체 queue에 들어갈 요소의 수
4. K번째 queue요소 제거 및 다른 리스트(result)에 삽입
5. result 출력

💡알고리즘 설계
deque를 사용하여 시간 초과 걸리지 않게 설정
리스트는 시간초과 뜨게 됨

1. N만큼 queue에 요소 삽입
2. K번째인지 체크 후 삭제 및 삽입
3. 큐의 마지막인 경우 다시 처음으로 돌아갈 것

💡기존 코드

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

queue = list(range(1, n + 1))
result = []
cnt = 0
i = 0

while len(queue) > 0:
    cnt += 1
    
    if cnt == k:
        result.append(str(queue[i]))
        queue.pop(i)  # queue에서 i번째 요소를 제거
        cnt = 0
    else:
        i += 1
    
    if i >= len(queue):
        i = 0

print("<",", ".join(result),">")

💡코드

from collections import deque
n, k = map(int, input().split())

queue = deque(range(1, n + 1))
result = []

while queue:
    for _ in range(k-1):
        queue.append(queue.popleft())
    result.append(queue.popleft())

print(str(result).replace('[', '<').replace(']', '>'))

💡시간복잡도
O(1)
deque니까 ..?

💡 틀린 이유
시간 초과 및 deque 사용 안하고 리스트로 풀려고 했다.
💡 틀린 부분 수정 or 다른 풀이
1. 처음 queue를 리스트로 만든 것을 deque로 변경해주기
2. 계속 for문으로만 하려고 했던 것을 while로 먼저 변경해주기
3. 출력 시 "<",">"로 변경하는 것을 잊어서 변경해주기
💡 느낀점 or 기억할정보
느낀점
deque가 생각보다 엄청 빠르고 리스트는 생각보다 더 느려서 놀랐다.
Queue문제에서는 deque를 사용하려고 해야겠다.