[코테 매일 풀기 19일차] 1202

[백준 11866 요세푸스 문제 0]

아이디어

👿 핵심 파악
- 한줄 요약: 원형으로 앉은 N명에서 K번째마다 제거해 순서 구하기
- 입력: N(사람 수), K(제거 간격)
- 출력: 제거된 순서 <a, b, c, ...> 형식

🧻 문제 분류

• 알고리즘: 구현, 큐 회전
• 자료구조: Queue(ArrayDeque)
• 시간 복잡도: O(n*k) -> N명 제거해 각각 k-1번 회전

💡아이디어 및 의사코드

Queue에 1~N 넣기 

반복 ( 큐가 빌때까지 ) : 
	//K-1명을 앞에서 빼서 뒤로 보내기 
	K-1번 반복: 
		poll()하고 offer() 
	//K번째 사람 제거 
	poll()해서 결과에 추가 

✅ 예외상황

• 마지막 원소 쉼표 처리

package boj_silver.p11866_요세푸스;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //이중 연결 리스트로 해야하나? -> 결국 생각 못함 ->  원형 큐는 poll()하고 offer()하는 연산
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        StringBuilder sb =  new StringBuilder();

        //Queue에 1~N 넣기
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i<=n; i++){
            q.offer(i);
        }// N = 7일때 q = {1,2,3,4,5,6,7}

        sb.append("<");

        while(!q.isEmpty()){
            //k-1명을 앞에서 뒤로 보내기
            for (int i =0; i< k-1; i++){
                q.offer(q.poll());
            }
            sb.append(q.poll());
            //마지막이 아니면 , 추가
            if(!q.isEmpty()){
                sb.append(", ");
            }
        }
        sb.append(">");
        System.out.println(sb);

        sc.close();

    }
}