[백준/Java] 1158 : 요세푸스 문제

사실 상 size가 정해지면 list를 만들 필요 없이 배열로 해도 된다. 하지만 이 문제에 대해서는 배열을 활용하기 위한 것이 아닌, list를 활용하여 문제를 풀어보기 위함이었다.

ArrayList를 활용할 것인가, LinkedList를 활용할 것인가에 대해 많은 고민과 테스트가 있었다. 우리가 흔히 알고 있는 각각의 장단점은 ArrayList에서 만큼은 값을 검색하는 능력이 빠르고, 값의 추가 삭제가 느린 대신에, LinkedList는 값을 검색하는 것이 느리며 값의 추가 삭제가 빠르다는 것이다.

그런데 문제를 풀어보면 풀어볼수록 이상한 결과가 나왔다. 요세푸스문제의 경우 값이 중간중간에 계속 빠지는 부분이 있다보기에 LinkedList를 활용하여 값을 관리하려고 했다. 하지만 ArrayList가 그럼에도 불구하고 빠른 속도를 보여주었다. 이는 어떤 예시입력을 하는지에 대해 확인할 수 없기 때문에 단정지을 수는 없지만, 이 부분에 대해서는 더 들여볼 생각이다.

위가 LinkedList, 아래가 ArrayList이다.

요세푸스 문제 성공

시간제한	메모리제한	제출	정답	맞힌사람	정답비율
2 초	256 MB	54683	26642	18980	48.138%

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

제출 답안

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.List;
class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        List<Integer> list = new ArrayList<Integer>();
        int index = 0;
        
        /* List안에 1부터 n까지의 값을 순서대로 넣는다. */
        for(int i = 1; i <= n; i++) {
            list.add(i);
        }
        
        /* 출력이 <3, 6, 1 ...> 와 같은 형식으로 출력되어야 하기 때문에 StringBuilder를 선언 */
        StringBuilder s = new StringBuilder();
        s.append("<");
        
        /* list 값이 없을 때 까지 반복 */
        while(!list.isEmpty()) {
        
        	/* index는 k-1만큼 점프하되, 인원수가 벗어나게 되면 현재 인원수만큼 나눈 나머지를 index로 설정 */
            index = (index + k - 1) % n;
            
            /* list가 1 남았을 때에는 마지막 수이므로 >로 마무리 해야한다. */
            if(list.size() > 1) s.append(list.remove(index) + ", ");
            else s.append(list.remove(index));
            
            /* 인원수를 list.size()로 하지 않고 n을 활용한 이유는 조금이라도 시간을 단축하기 위함이다. */
            n--;
        }
        s.append(">");
        System.out.println(s);
    }
}