[JAVA] 백준 - 1158) 요세푸스 문제

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

문제 풀이 : https://github.com/jeygeon/baekjoon/blob/master/src/DataStructures/_1158/Main.java

 

이번 문제를 풀 때는 어려웠던 부분이 몇 가지 존재했던 것 같다.

 

사실 일단 문제를 이해하는 것 부터가 어려웠는데, 요세푸스 문제가 뭔지 구글링 해본결과 예를들어 (7, 3) 요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4> 가 된다.

 

(7, 3) 에서 요세푸스 순열을 구하려면 1, 2, 3, 4, 5, 6, 7을 순서대로 놓고 3번째 순서마다 제외를 하는 것이다.

 

위에서 3번째 숫자는 3이고 3을 제외한뒤 다음 3번째 순서는 6이다.

 

그럼 3과 6을 제외하고 6 다음부터 그 다음 3번째 숫자는 7 > 1 > 2 순서이기 때문에 2가 된다.

 

이렇게 해서 나온 결과가 <3, 6, 2, 7, 5, 1, 4>가 되는 것이다.

 

이제 이것을 코드로 구현하면 되는데, 문제에서는 사람이 원을 이루면서 앉아있다고 표현했지만 내가 위에서 설명한 대로 일자로 쭉 숫자를 나열한 뒤 큐를 이용해서 문제를 풀면 됐었다.

 

내가 처음 문제를 풀 때는 ArrayList를 이용해서 문제를 풀려고 했는데 get(), remove(), add() 메소드 등 너무 사용해야 될 메소드가 많아져서 LinkedList를 이용해서 구현된 큐를 사용했다.

 

그랬더니 나오는 메모리 초과..🥲

 

문제는 틀리지 않았지만.. 메모리를 줄일수 있는 방법이 뭐가 있을까 하다가 ArrayDeque는 큐의 구현체 중 하나이지만 배열을 사용하기 때문에 메모리 사용량에서 LInkedList보다 더 효율적으로 관리되지 않을까 하고 변경 하였다.

 

변경 한 뒤 문제는 맞았지만 그 전에 몇 번 틀린적이 있는데, 큐에서 마지막 요소 처리하는 부분이 문제였다.

 

코드를 작성 한 뒤 7 3 을 입력하면 정상적으로 <3, 6, 2, 7, 5, 1, 4>가 나왔지만 1 1을 입력하니 <1, 로 결과가 출력되었다.

 

만약 맞는거 같은데 계속 틀리다고 나온다면 이런식으로 반례를 찾는 것이 도움이 많이 되었다.