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

in Problem Solving on BaekJoon


날짜: 2021년 5월 31일
소요 시간: 1시간 42분 12초
카테고리: 자료구조, 큐
태그: silver.5, 1158 , 파이썬

백준 1158 - 요세푸스 문제

입출력 예시

예제 입력예제 출력
7 3<3, 6, 2, 7, 5, 1, 4>

내가 적은 코드

N,K = map(int, input().split())

T = 0
que = []
arr = [i for i in range(1,N+1)]
while len(arr) != 0:
    T = (T + K-1) % len(arr)
    que.append(arr[T])
    arr.pop(T)
    N -= 1
print('<' + ', '.join(map(str,que)) + '>')

# 나름 큐로 풀어보겠다고 풀었던 코드  

N,K = map(int, input().split())

que = []
arr = [i for i in range(1,N+1)]
while len(arr) != 0:
    i = 1
    while i < K:
        arr.append(arr[0])
        arr.pop(0)
        i += 1
    que.append(arr[0])
    arr.pop(0)
print('<' + ', '.join(map(str,que)) + '>')

풀이 과정

사실 반복문을 통해 한바퀴 돌 때 마다 제거하는 방식보다 큐를 활용하여 한번 풀어보려 했으나 파이썬에서 (내 나름대로 한번) 큐를 구현해서 실행시켰더니 시간 초과가 났다.

반복을 통해 + K-1) % len(arr) 번째씩 더해가며 원소를 pop하고 그 원소를 que에 저장했다.

베스트 코드

n, m = map(int, input().split())
l = list(range(1, n + 1))
r = []
index = 0

while l:
    index = (index + m - 1) % len(l)
    r.append(str(l.pop(index)))

print('<', ', '.join(r), '>', sep='')

반성

  • 알고리즘 적으로 베스트 코드와 다르지 않았다는 점에서 실력이 늘어감을 느낀다.
  • 시간 복잡도를 줄인 큐를 통해 풀 수 있는 방법을 찾지 못하였다.


© 2021. by hminkim