백준 1158번 - 요세푸스

 

 

• 접근 방식

문제를 보고 패턴(k값)이 있는 원형수열(?)임을 생각하고 전에 풀어봤던 풍선터뜨리기 문제가 떠올라서 그 문제 풀이와 같이 front와 back을 바꿔 원으로 돌아가는 패턴을 구현할 수 있는 덱(deque)을 통해 접근해 보았다.

 

 

 

• 논리 흐름(알고리즘)

주어진 사람 수 만큼의 숫자를 넣고, 주어진 key-1번(숫자가 pop되면서 1번 실행) front값을 back값으로 보내주면 front값에 순서대로 구할 값이 남게 된다. 

러시안룰렛처럼 key번 돌리고 총알을 쏜다고 생각하면 된다. 총알이 다 떨어질 때까지 이 과정을 반복하면 답이 나온다.

마지막 출력 조건에서 삐끗했는데, 반복문에 단순히 ", "출력을 더해주면 마지막에

<3, 6, 2, 7, 5, 1, 4, >로 출력되기 때문에 따로 조건문을 걸어주었다.