알고리즘 연습 심화 - 5

요세푸스 문제를 풀어보았다.

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

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

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

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

이 문제를 풀기 위해서 일단

코드를 어떻게 짜야할지 고민을 해 보았다.

N K 입력받기
1번부터 N번까지 순열 큐 A 만들기
K번째 큐를 빼서 큐 B에 넣기
만약 큐 A의 길이가 K보다 작아지면 K - A 의 길이 = K 로 바꿔서 다시하기
큐 A의 길이가 0이 될때까지 루프. 0이 되면 종료.
큐 B 출력하기

이런식으로 짜면 될 것 같다.

Scannse scna = new Scanner(System.in); //스캐너를 불러오고

int N = scan.nextInt(); // N명의 사람이 원을 그릴 때 N명 입력받기
int K = scan.nextInt(); // K번째 사람 빼기, K를 입력받기

Queue<Integer> queue = new LinkedList<>();
// 이부분이 이해가 잘 안되었는데, 
// StringBuilder sb = new StringBuilder(); 
// 와 같은 말이라고 한다.

String s = ""; //위의 따로 설명한 말과 같은 의미이다.

for (int i = 1; i <= N; i++){
            queue.add(i);

        }
        while(!queue.isEmpty()){
            for(int j =0; j< K-1; j++) {
                int in = queue.poll();
                queue.add(in);
            }
            //sb.append(queue.poll()+"\n");
            s+= queue.poll()+"\n"; // 이 부분도 이해가 잘 안되었는데, 위의 주석처리한 부분과 같은 의미이다.

        }
        //System.out.println(sb.toString());// K번째 값을 출력하고 뺀다
        System.out.println(s); // 위의 주석처리한 부분과 같은 의미이다.

    }
}

이렇게 코드를 짜 보았는데,

모르는 부분이 많아서 이해를 돕는데에 다른 분의 도움을 받았다.

이렇게 풀어보고 또 다시 백지로 이 문제를 다시 풀어 보았는데,

아무것도 안 보고 온전히 풀기 아주 어려웠다.

새로 푸는것이 꽤 나에게 도움 된다는 것을 깨달았다.