[백준] 1158번 요세푸스 문제 - Python(파이썬)

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

1158번: 요세푸스 문제

 

문제

 

21.02.16 접근법

 

list보다 효율성있는 deque 선택

 

crt로 deque위치 현재 위치 파악

: 1씩 더하고, 맨 끝으로 가면 처음인 0번째로 초기화

 

ck로 T번째인지 체크

: 1씩 더하고, T가 되면 카운트 초기화

 

 

21.02.16 코드

from collections import deque

N,T=map(int,input().split())
arr=deque([i for i in range(1,N+1)])
ck=0
crt=-1
answer=[]

while arr:
    if(crt==len(arr)-1):
        crt=0
    else:
        crt+=1
        
    ck+=1
    if(ck==T):
        ck=0
        answer.append(arr[crt])
        arr.remove(arr[crt])
        
        if crt==0:
            crt=len(arr)-1
        else:
            crt-=1

print('<',end='')
for _ in range(N):
    if _==N-1:
        print(answer[_],'>',sep='')
    else:
        print(answer[_],end=', ')

 

21.07.21 접근법

 

deque의 순환을 활용

 

1. 앞에서 K-1번째를 뒤로 보내 K번째를 맨 앞에 위치

2. popleft를 사용해 앞으로 온 K번째 제거

3. 1과 2를 반복

 

 

21.07.21 코드

from collections import deque

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

deq=deque([i for i in range(1,N+1)])

print('<',end='')
for _ in range(N):
    deq.rotate(1-K)

    if _!=N-1:
        print(deq.popleft(),end=', ')

    else:
        print(deq.popleft(),end='')
print('>')