1158 요세푸스 순열 JAVA

 

이런 순열을 처음 접해봤지만, 절대 어려운 문제는 아니였다. 직전에 풀이했던 카드와 매우 유사하였다.

 

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

 

 

바로 코드를 보여주겠다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new LinkedHashSet<>(N);
        int tmp = 0;

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

        for(int i = 1; true; i++) {
            if(queue.size() == 0)
                break;

            if(i % K == 0)
                set.add(queue.poll());
            else
                queue.offer(queue.poll());
        }

        Iterator<Integer> it = set.iterator();
        StringBuilder sb = new StringBuilder("<");

        for(int i = 1; it.hasNext(); i++) {
            sb = (i != set.size())
                    ? sb.append(it.next()+", ")
                    : sb.append(it.next()+">");
        }

        System.out.println(sb.toString());
    }
}

 

오히려 나는 예시 출력형식으로 출력하는게 약간 더 까다로웠는데.. 일단 그건 마지막에 얘기하고 싶다.

 

먼저 나는 이 문제를 다음과 같이 해석하였다.

기본적으로 요세푸스 순열은 1~N까지의 모든 데이터를 순회하며, K번째마다 해당 데이터를 지우고, 모두 지워질때까지 반복하는 것이다. 이 문제는 이러한 로직을 마피아게임?에 비유했다고 생각하였다.

 

이번에도 내가 이 문제를 구현해내기 위하여 어떠한 순서로 풀어냈는지 설명을 해보려고 한다.

 

1.사용자에게로부터 N과 K를 입력받는다.

2.N을 큐 자료구조 형식을 이용하여 값을 초기화한다.

3.무한루프를 돌리는데, 큐에 남은 데이터가 하나도 없는 경우, 반복을 멈춘다.

4.제거되는 순서는 배수를 이용하여 결정하고, 그 배수가 아닌 경우, 맨 뒤로 보낸다.

 

이 과정을 구현하면, 요세푸스 순열을 구현해낼 수 있는데, 문자열에 대해서 조금만 얘기해보고 싶다.

우선 문자열을 사용해야할 때, 가장 많이 쓰이는 클래스가 String이다. 하지만 이 클래스는 편리하다는 장점과 동시에

잘못하면 성능상 이슈가 생길 수 있다는것이다. String 클래스는 immutable 즉, 변경 불가능한 클래스인데 이 말은

내용을 변경할 수 없다는 것이다. 당연히 덧셈 연산자를 이용한 결합이나 메서드를 통한 짤라내기 등은 모두 변경이 된것이 아닌 새로운 String 인스턴스를 생성하여 다른 주솟값을 넣은 것이다. 따라서 문자열의 변경이 많은 경우엔, String의 사용은 자제하는게 좋다.

 

그럼 변경 가능한 클래스는 없을까? 

당연히 있다. StringBuilder 와 StringBuffer 클래스인데, 이 두 클래스는 내용 변경이 가능한 클래스로써, 서로 기능의 차이는 없지만 동기화의 차이가 있다.StringBuilder는 동기화가 되어있지 않은 클래스로써 단일 쓰레드에서 유용하고, 멀티 쓰레드에선 StringBuffer를 사용하면 된다.