[백준] 11866번
요세푸스 문제 0
PYTHON
이 문제를 접근할 때, 오해하게 되는 부분이 있다.
"문제에서 N명의 사람이 주어지고 K번째 사람을 제거한다" 라고 쓰여있기 때문에
만약 사람이 K 명 이하가 되면 어떡하지? 라는 오해를 한다.
처음에 그래서 문제에서 주어지지도 않은 규칙을 혼자 생성해서 문제를 풀다가 오답이 나온 경우가 있다.
예제 출력을 보고
K 명 이하로 사람이 줄어들면 맨 뒤의 사람부터 제거하는 거구나 라고 생각했다.
당연히 오답이었다.
문제를 해결할 때, 절대로 문제에서 주어지지 않은 규칙을 혼자 판단해서 생성하면 안된다.
그럼 다시 해석을 해보자.
N 명의 사람이 주어지고 K번째 사람을 제거한다.
이걸 queue, deque 자료구조의 관점에서 생각해보면
K-1만큼 앞의 원소를 제거하고 뒤에 다시 삽입하는 연산을 반복했을 때,
큐의 가장 앞의 원소를 제거하면
큐에서 K번째 원소를 제거하는 것으로 해석할 수 있다.
실제로 K명 이하이기 전에 K번째 원소를 제거하는 방식도 동일하다. K-1번 삭제하고 뒤에 삽입하면 원형 탁상에서 K번째 원소를 제거할 수 있다.
소스 코드를 살펴보자.
입력 데이터의 크기가 크지 않기 때문에 이중 포문을 사용하더라도 시간 초과가 발생하지 않는다.
여기서 삭제되는 원소를 순서대로 리스트에 삽입하지 않고
그 순간에 출력하여
리스트에 사용되는 공간, 리스트에 삽입하는 시간을 절약하였다.
Whiplash We Flash