[백준] 11866번

문제출처: https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

요세푸스 문제는 알고리즘 문제 중 queue 문제로 분류된다.

그래서 queue에 대해 간략히 되짚어보고 가본다.

queue는 선입선출(FIFO), 즉 먼저 들어온 값이 먼저 나가는 방식이다.

코드로 구현하면 아래와 같다.

11866번의 문제 내용이다.

동그란 원을 그리고 순서대로 죽죽 그어 제거해보면 금방 이해할 수 있는 문제다.

문제는 코드를 구현하는 과정이지만...

쉽게 봤다가 원하는대로 안나오고 뒷부분으로 갈수록 엉뚱한 값이 pop 되어서 당황했다.

​

우선 n, k값을 받고 1부터 N번째까지 숫자를 순서대로 append해준다.

참고로 속도를 빠르게 하기위해 파이썬 라이브러리에 있는 deque을 사용했다.

정답 값을 받을 ans 배열을 선언한다.

​

다음으로 쓰는 반복문 내의 또다른 반복문이 필요한데, 이 부분이 핵심이다.

이걸 제대로 작성하지 못해서 돌고 돌아 헤맸다.

처음에는 queue 내에서 원하는 k번째 수를 pop 시키고 ans에 갖다꽂아버리는 작업을 했으나,

그렇게 하면 배열 순번이 하나씩 밀려 뒤로 갈수록 엉뚱한 수가 pop된다.

​

최종 코드에서 사용한 원리는 다음과 같다.

for문을 배열 내에서 원하는 값이 0번째로 나올때까지 돌린다.

그 안에서 현재 0번째에 있는 값을 뒤로 차례로 넣고, 이후 0번째에 있는 값을 pop시킨다.

왼쪽 값부터 pop해야하기 때문에 popleft를 사용한다.

이것이 queue의 FIFO 성질을 이용한 것이다.

​

for문이 끝나면 이제 0번째에 있는 값은 내가 제거하고 싶어하는 값이다.

이 값을 pop해서 ans 배열에 append한다.

그럼 ans배열에는 0번부터 차곡차곡 순열값이 쌓인다.

​

이 전체 반복문을 queue가 0(False)이 될 때까지 반복해주면 된다.

모든 반복문이 끝나고나면, ans 값을 출력한다.