파이썬 백준 1158 : 요세푸스 문제

 

문제

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

 

 

풀이

 

Sol1 : 리스트 이용

N,K =map(int,input().split(' '))
people_list=[i for i in range(1,N+1)]
result=[]
index = 1
i=0
while len(people_list)>0: #list의 원소가 남아있을때까지 반복
    if i>=len(people_list):
        i=0
    if index%K==0 :
        result.append(people_list[i])
        people_list.pop(i) #K번째 사람 pop
    else:
        i+=1
    index += 1

print("<",end='')
for i in result[:-1]:
    print(i,end=', ')
print(result[-1],end=">")

• - list에 원소를 저장하고 원소 이동할때마다 index를 하나씩 증가함
• index가 K의 배수일 경우 pop진행 및 result에 저장

 

Python 3결과 시간초과 발생

 리스트의 pop(0)은 요소를 제거한 후 나머지 요소들을 모두 한 칸씩 앞으로 당겨야 하므로 시간 복잡도가 O(n)

덱의 popleft()는 O(1)의 시간 복잡도를 가지므로 매우 빠르게 요소를 제거할 수 있음 -> 덱으로 구현

 

 

Sol2 : 덱 이용

from collections import deque

N,K =map(int,input().split(' ')) #N, K입력 받기
people_deque=deque() #빈 deque생성
people_deque.extend(i for i in range(1, N + 1))
result=[] #출력할 결과
index = 1
while len(people_deque)>0:
    if index%K==0 :
        result.append(people_deque.popleft())
    else :
        people_deque.append(people_deque.popleft())
    index += 1
print(str(result).replace('[','<').replace(']','>'))

• if index % K == 0:에서 index는 현재 차례를 나타내며, 이때 index가 K의 배수인 경우에는 K번째 사람을 제거
   people_list의 맨 앞에 있는 사람을 result 리스트에 추가하고 popleft() 메서드를 사용하여 해당 사람을 제거
• 그렇지 않은 경우, 즉 K의 배수가 아닌 경우에는 K번째 사람이 아니므로 현재 맨 앞에 있는 사람을 people_list의 맨 뒤로 옮김
  이를 위해 popleft() 메서드로 현재 맨 앞에 있는 사람을 제거한 후, append() 메서드를 사용하여 다시 people_ deque 의 맨 뒤에 추가
• index를 1 증가시켜서 다음 차례를 나타내고, 다음 차례에서도 같은 과정을 반복