[백준] 1158번: 요세푸스 문제

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

 

💡문제 분석 요약

원을 이루며 앉아있는 N명의 사람 중 K번째 사람을 제거하는 과정을 N번 반복하여 제거되는 순서를 출력하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 256MB

💡알고리즘 설계

큐를 이용.

1. 1~N까지의 숫자를 큐에 offer
2. K-1번째 까지 맨 앞 값을 poll 한 다음, 맨 뒤에 offer
3. K번째 값을 poll 하여 결과 문자열에 추가
4. 2,3번을 N번 반복

💡코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] r = br.readLine().split(" ");
        int N = Integer.parseInt(r[0]); int K = Integer.parseInt(r[1]);
        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i<=N; i++){
            q.offer(i);
        }
        sb.append("<");

        while(N-- > 0) {
            for(int i=0; i<K-1; i++) q.offer(q.poll());
            sb.append(q.poll());

            if(N!=0) sb.append(", ");
        }

        sb.append(">");
        System.out.println(sb);
    }
}

💡시간복잡도

메인 루프의 시간복잡도가 O(N), 루프 내에서 O(K-1)의 시간복잡도.

따라서 전체 시간복잡도는 O(N*K) 이다.

💡 느낀점 or 기억할정보

큐를 이용하면 간단히 해결할 수 있는 문제였지만, 방법을 생각해내는 데 오래걸렸다.