[BAEKJOON] - 1158번 : 요세푸스 문제

1158번 문제 링크

이번 문제는 이전에 풀었던 실버Ⅱ 문제들에 비해서 상대적으로 쉬웠던 문제였다. 처음에 원의 형태라고 하여, 큐를 2개를 사용하여 값을 순환해야 하는 문제라고 생각했지만, 2개를 사용할 경우 조건문이 추가되어 로직이 복잡해지게 된다.

다시 한번 생각해보니 큐 하나로도 해당 요세푸스 순열을 만들 수 있었다.

큐는 선입선출로 먼저 들어간 요소가 먼저 나오는 자료 구조이다. 큐에서 뽑아낸 요소를 다시 큐에 집어넣는 방식으로 구현해주면, 원의 모형으로 순환되는 형태로 값을 처리할 수 있게 된다.

문제를 읽어보면, 순서대로 K값에 위치한 요소를 제거하라고 되어 있으므로, K-1 값 동안 반복하여 큐에 다시 넣어준 뒤, K번째 값은 뽑아서 StringBuilder에 담는 형식으로 구현하였다.

😀 성공

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
    public static void main(String[] argas)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        br.close();
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i <= N; i++){
            q.offer(i);
        }
        
        StringBuilder sb = new StringBuilder("<");
        while(!q.isEmpty()){
            for(int i=0; i < K-1; i++){
                q.offer(q.poll());
            }
            sb.append(q.poll()).append(", ");
        }
        
        sb.replace(sb.length()-2,sb.length(),">");
        System.out.println(sb);
    }
}

📖 참고

Java SE 17 & JDK 17 버전 공식 문서

• StringBuilder에 replace() 함수는 위 문서에도 나와있듯이 start 요소 포함, end 요소를 제외한 값을 지정하여 str 값으로 바꿔준다.