[백준][11866] - 요세푸스 문제 python 파이썬

요세푸스 문제 0 - 11866

문제 링크

11866번: 요세푸스 문제 0

문제설명

이 문제를 푸는 방법에는 여러가지가 있겠지만, deque를 이용한 방법은 시간복잡도 측면에서도 효율적입니다.

 

먼저 문제 설명을 간단히 해보면, 1부터 N까지의 수가 순서대로 있고, 매번 K번째 수를 제거하는 과정을 반복하여 남은 수들을 모두 출력하는 것입니다.

from collections import deque

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

deq = deque([i for i in range(1,N+1)]) # 데크 안에 리스트 넣기 (이 부분 모르면 아래 링크!)

result =[]

for _ in range(N) :
    deq.rotate(-K) # -K만큼 배열을 rotate
    result.append(deq.pop()) # 오른쪽에 있는 배열을 pop한 것을 결과 값에 넣어준다.

print('<'+str(result)[1:-1]+'>')

 

파이썬 컴프리헨션 - "간단한 리스트 생성 및 리턴" 괄호 안 포문

 

 

이 코드를 작성하면서 사용한 파이썬 내장 모듈인 collections 모듈의 deque 클래스는 큐(Queue) 자료구조를 구현할 때 유용하게 사용되는 클래스입니다.

 

deque 클래스는 이 큐의 양쪽 끝에서 삽입/삭제가 모두 O(1)의 시간복잡도로 가능합니다.

이 문제를 풀면서 공부해야 할 내용은 큐 자료구조와 deque 클래스에 대한 이해입니다.

 

그리고 파이썬에서 deque 클래스를 활용하여 큐를 구현하는 방법에 대해서도 공부해보면 좋을 것 같습니다.

🙇