[알고리즘] 백준 1158번 - 요세푸스 문제

문제

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

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)

7 3

출력

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

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class A1158 {

    private static String calc(List<Integer> list, int k) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        int n = 0, i = 0; // n = 증가 카운트, i 현재 인덱스 값
        int len = list.size();

        sb.append("<");
        while(len != 0) {
            if(i >= len || i < 0) {
                i = 0;
            }
            if(n > 0 && n % k == 0) {
                Integer pop = stack.pop();
                list.remove(pop);
                sb.append(pop).append(", ");
                --len; --i;
                n = 0;
                continue;
            }
            
            stack.push(list.get(i));
            ++n; ++i;
        }
        
        sb.deleteCharAt(sb.length() - 1).deleteCharAt(sb.length() - 1).append(">\n");

        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter consoleWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        List<Integer> list = new ArrayList<>();

        String[] split = reader.readLine().split(" ");
        int k = Integer.parseInt(split[1]);
        int len = Integer.parseInt(split[0]);
        for(int i = 0; i < len; i++) {
            list.add(i + 1);
        }

        consoleWriter.write(calc(list, k));

        consoleWriter.flush();
        consoleWriter.close();
        reader.close();
    }


}

내가 푼 방식

1. 먼저 n만큼 ArrayList에 숫자를 넣어준다.
2. 배열의 길이가 0이 될때 까지 while문을 돌려주는데
3. 이후 stack에 계속 현재 i값을 넣어준다.
4. ArrayList를 계속 순회하면서 i값을 검사해주는데 이때 조건은
   배열의 길이와 같거나 초과했을 때 i가 0보다 작을 경우이다.
5. n의 길이가 1이상이고 n이 k배수일 때 스택에서 하나를 뽑아 ArrayList에서 지워주고 문자열에 이어붙인다

StringBuilder

thread-safe하지 않아도 되는 상황에서 문자열 연산을 할 때
'+' 연산을 하는것 보다 StringBuilder로 append하는게 더 빠르다.
이유는 String 객체는 immutable object이다. (불변 객체)
그러므로 +연산을 해서 문자열을 결합 할 시 새로운 인스턴스를 만들어 반환하는 말도안되는 오버헤드가 발생한다.

String a = "Hello "; // 0x0000;
String b = "World"; // 0x0005;
String c = a + b; // 새로운 인스턴스 0x1100

하지만 StringBuilder, StringBuffer(thread-safe)같은 경우 내부적으로 가변크기 배열을 사용하여 문자열을 추가한다.
n길이의 문자열 변수가 append될 경우 n만큼의 크기가 있다면 그대로 복사해서 넣고 아니라면 현재 가변 배열의 길이 * 2를 해서 크기를 증가시키고 넣는다.
Java에서 String관련해서는 무조건 알고있어야 하니 나중에 다시 다뤄보도록 하자.