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

풀이 방법

이 문제는 조세퍼스 순열이라는 문제입니다. 처음에 이 문제를 보고 큐 혹은 리스트를 사용하면 될 것 같다는 생각을 했습니다. 그래서 생각을 실천하기 위해서 코드를 작성했습니다. 하지만, 계속 M번째 사람을 제거하는 과정을 어떻게 구현할 수 있을까가 문제였습니다.

이 부분을 고민하게 된 이유는 리스트의 성질을 이해하지 못한 부분에서 발생했습니다. 리스트에서 요소를 삭제하면 빈 곳은 다른 요소들이 채우게 되면서 자연스럽게 빈 자리를 채워줍니다. 당연히 인덱스도 변경이 일어나게 됩니다. 이런 특성을 이해하고 나서 문제를 접근하는 것이 더 편해졌습니다.

저는 LinkedList라는 자료구조를 사용하고 이 list에 N번까지의 사람을 채워넣고 그 다음에 M번째 사람을 계속해서 제거하였습니다. 사람을 제거하면서 StringBuilder 객체에 표시를 하였고, list의 사이즈는 계속 줄어들고 제거해야 할 index는 계속해서 증가하기 때문에 index>list.size의 문제가 발생합니다. 이러한 문제를 해결하기 위해서 index가 list의 size를 넘어가게 되면 index를 list의 size로 나눈 나머지를 index로 사용하게 됩니다. 왜냐하면 이 문제에서 사람들은 원을 이루면서 앉아있는 상황이기 때문에, 시작과 끝이 연결되어 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BOJ1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        LinkedList<Integer> list = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder("<");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for(int i=0;i<N;i++){
            list.add(i+1);
        }

        int index=0;
        while(!list.isEmpty()){
            index +=(M-1);

            if(index>=list.size()){
                index = index % list.size();
            }

            sb.append(list.remove(index)+", ");

        }


        //bw.write(sb.toString()+"\n");
        String result = sb.substring(0, sb.length()-2);
        bw.write(result+">");
        bw.flush();
        bw.close();
    }
}

배운 점

문제를 보고 사용할 수 있는 자료구조를 바로 생각해 내는 방법을 배웠습니다. 이러한 과정이 쉽지만은 않지만, 계속해서 노력하면 실력이 늘 것이라고 생각합니다.:)