[백준] #1158 - 요세푸스 문제

2023/7/12-13

실버 4

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

1158번: 요세푸스 문제

 

 

🔎 분석

간단할거라고 생각했던 문제. 고치고 나니까 실제로 코드도 간단했고 처음 생각한 대로 K번째 앞에 있는 숫자들을 전부 큐의 뒤에 push하고 K번째 숫자를 꺼내어 res_list에 저장하면 되는 간단한 문제였다.

 

나는 이 방법 말고 실제 K번째를 구하고, 현재 index를 prev_idx로 저장해뒀다가 그걸 이용해서 다음 K번째의 index를 구하는 방식으로 하였다. 이렇게 하면 예외 상황들이 생기게 되는데, prev_idx+K-1의 값이 전체 배열 길이를 넘어갈 수 있다. 이럴 경우에 대비하여 idx의 값에 %len(ppl_list)를 적용하여 길이를 넘어서지 않도록 하였다.

 

생각보다 간단하게 해결할 수 있었다. 근데 코드가 꼬여서 오래 걸렸다.

 

 

💻 코드

from collections import deque

N, K = map(int, input().split())
# queue 배열 만들기
ppl_list = deque([i for i in range(1, N+1)])
res_list = []

next_num = K
prev_idx = 0
prev_num = -1

# 방법1 -> 코드는 복잡하지만 시간이 훨씬 짧음
for _ in range(N):
    if len(ppl_list) == 1:
        res_list.append(ppl_list[0])
        break
    idx = (prev_idx + (K-1))%len(ppl_list)
    prev_idx = idx

    num = ppl_list[idx]
    
    res_list.append(num)
    ppl_list.remove(num)
    prev_num = num


# 방법2 -> 코드는 짧지만 시간이 10배 늘어남
# for _ in range(N):
#     for _ in range(K-1):
#         # K번째가 맨 앞에 오도록 그 앞 수들을 가장 뒤로 push하기
#         ppl_list.append(ppl_list.popleft())
#     res_list.append(ppl_list.popleft())
    
result = ''
for idx, num in enumerate(res_list):
    if idx == 0 and idx == len(res_list)-1:
        result += '<' + str(num) + '>'
        break
    if idx == 0:
        result += '<' + str(num) + ', '
    elif idx == len(res_list)-1:
        result += str(num) + '>'
    else:
        result += str(num) + ', '
print(result)