[백준 알고리즘] 1158번: 요세푸스 문제 (Python)

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

1158번: 요세푸스 문제

 

소스코드

 

풀이

자료구조 중 하나인 Queue(큐)를 사용하면 어렵지않게 해결할 수 있는 문제입니다.

기본적으로 큐는 FIFO(First in First out, 선입선출) 성격을 가지고 있습니다. 이러한 성질을 활용하여 배열을 앞에서부터 순서대로 제거해줄 수 있습니다. 

 

파이썬에서 큐를 사용하기 위해서는 

'from collections import deque'로 큐를 임포트해줘야 합니다. 

 

n까지의 입력받은 배열을 '큐' 자료구조인 a 저장해줍니다.  

ans 리스트는 문제의 정답인 제거되는 사람의 순서를 저장해주고 출력하기 위한 배열입니다. 

 

이중 for문을 사용하여 k-1 번째 사람까지 popleft() 함수를 사용하여 큐에서 제거한 뒤 append() 함수로 다시 배열에 추가해줍니다. 제거하고자 하는 사람의 순서인 k 번째 사람은 큐에서 제거해준 뒤, 다시 추가시키지 않고 정답을 구하기 위한 배열인 ans에 추가해줍니다. 이렇게 된다면 첫 반복문을 돌았을 때 큐에는 4,5,6,7,1,2가 저장되어 있고, ans에는 3이 저장되어 있습니다. 

 

위와 같은 과정을 n 번 반복해주면 ans에 제거된 순서가 저장됩니다.

 

출력 부분이 조금 까다로울 수 있는데, print문에 end 옵션은 기본값인 줄바꿈 (\n) 없이 사용자가 원하는 문자를 사용하여 출력할 수 있습니다. 그렇기에 저는 end 옵션에 ', '  쉼표와 공백을 주어 출력 조건을 맞춰줬습니다 !