[백준] 요세푸스 문제

안녕하세요.
방금 푼 백준 1158번 요세푸스 문제의 풀이를 작성해보겠습니다.

문제

요약
1번부터 N번까지 차례로 원을 이루면서 위치하고, K번째마다의 사람을 한명씩 제거해가며 순열을 만듭니다.
N번까지의 사람이 모두 제거되면 요세푸스 순열이 만들어지고, 그 값을 return 합니다.

처음으로 생각한 방법

문제에서 말한 원을 이루면서 앉아있다는 것을 보자마자, LinkedList 일까 아니면 Queue 일까 고민했습니다.
그런데, 구현적인 면에서 LinkedList 로도 구현할 수 있을 것 같지만 Queue 가 훨씬 간단할 것 같아 Queue 자료구조를 사용해서 풀어서 통과했습니다 !

코드 설명

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String result = "<";
    Queue<Integer> queue = new LinkedList<>();

    int N = sc.nextInt();
    int K = sc.nextInt();
    int count = 1;

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

    // ...
}

위 코드는 메인 함수의 초반 코드입니다.
입력 수가 N 과 K 두 숫자이므로 버퍼의 사용 없이 Scanner 로 처리했습니다.
그 후에 1부터 N까지 큐에 넣어줍니다.

public static void main(String[] args) {
    // ...

    while (!queue.isEmpty()) {
        count %= K; // count == K 라면 0
        if (count++ == 0) { // 조건 처리와 동시에 후위 연산자를 사용해 count+1 처리를 해준다.
            result += queue.poll() + ", ";
            continue;
        }
        int num = queue.poll();
        queue.offer(num);
    }

    result = result.substring(0, result.length()-2) + ">";  // 마지막 숫자의 ", " 부분을 제거해주고 ">"를 추가해준다.
    System.out.println(result);
}

그 후 반복문을 순회하는데, 큐가 빌 때까지 순회합니다.
큐가 비었다는 것은 모든 사람을 요세푸스 순열로 제거했다는 뜻입니다.

count 변수는 몇 번째인지 체크하는 변수입니다.
따라서 먼저 K 로 % 연산을 해준다면 몇번째인지 정수로 세팅될 것입니다.

만약 count 가 0이라면 K 번째 사람이라는 뜻이니 result 문자열에 해당 사람이 몇 번 사람인지 추가하고 반복문의 처음으로 돌아갑니다.
count 가 0이 아니라면 K 번째 사람이 아니니 큐의 front에 있는 값을 rear에 다시 넣어줍니다.

위의 로직을 while 반복문이 끝날 때까지 반복하면 요세푸스 순열이 만들어질 것입니다.

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String result = "<";
        Queue<Integer> queue = new LinkedList<>();

        int N = sc.nextInt();
        int K = sc.nextInt();
        int count = 1;

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

        while (!queue.isEmpty()) {
            count %= K; // count == K 라면 0
            if (count++ == 0) { // 조건 처리와 동시에 후위 연산자를 사용해 count+1 처리를 해준다.
                result += queue.poll() + ", ";
                continue;
            }
            int num = queue.poll();
            queue.offer(num);
        }

        result = result.substring(0, result.length()-2) + ">";  // 마지막 숫자의 ", " 부분을 제거해주고 ">"를 추가해준다.
        System.out.println(result);
    }
}

마무리

문제를 풀기 전에 한 9달 전쯤에 풀었던 문제라는 것을 알았습니다.
하지만 그 때는 몇 번 시도한 후에 실패로 두고 넘어간 것인지 실패 라벨이 붙어있었습니다..

9달 전보다 자료구조에 대한 이해와 알고리즘 문제 이해 능력이 향상했다고 긍정적으로 생각하기로 했답니다! :)
이번 포스팅도 읽어주셔서 감사합니다 ~!