[백준/1158] 요세푸스 문제 | 파이썬 연결리스트 | N번째 원소

요세푸스 문제

---

2년 전 풀었던 요세푸스...! 다시 풀려니까 로직은 생각나는데 정확한 구현이 떠오르지 않아 다시는 까먹지 않으려고 포스팅한다. (문제 바로 가기)

 

알고리즘

---

순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

 

계속 해서 K 번째 사람을 제거하는데, 여기서 문제는 제거된 K를 제외하고 배열을 재생성해야 한다.

• 이 문제의 연산 범위는 (1 ≤ K ≤ N ≤ 5,000)이며, Python은 1초에 약 5천만번의 연산이 가능하다.
• 배열 순회하면서 K를 찾고, 배열을 재생성해도 O(N**2) 즉, 5000**2 = 2500만번 정도 수행한다.
• 따라서 연산마다 배열을 재생성해도 충분한 시간이다.

 

전체 코드

---

import sys;input=sys.stdin.readline

# 1. 값을 [0] + 입력으로 받아서 인덱스가 1부터 시작하도록
n,k = map(int, input().split())
li = [i for i in range(1, n+1)]

# 2. 인덱스 값을 (idx+k)%k
idx = 0
res = []
for _ in range(n):
    # 요세푸스 순열 규칙으로 리스트를 순회하기 위한 인덱스 점화식
    idx += (k-1)
    idx %= len(li)

    # 요세푸스에 따른 새로운 순열 생성
    res.append(str(li[idx]))
    li.pop(idx) # O(N)

print("<", ', '.join(res), ">", sep="")

 

알게된 점 및 정리

---

• 리스트의 'N번째' 인덱스는 %len(arr) 형태로 구할 수 있다.
• 파이썬의 pop()은 파라미터가 없으면 리스트 마지막 요소를 추출하며 복잡도는 O(1)
  
  • pop(i)와 같이 파라미터 값을 주면 복잡도는 O(N)
  • 파이썬은 배열이 없고 연결 리스트이므로, 연결 리스트의 검색 연산 복잡도를 갖는다.