[Java] 백준(실버-4) 1158번 - 요세푸스 문제

문제 풀이

---

이번 문제는 큐를 이용해 문제의 요구사항을 구현하면 되는 문제이다.

아이디어 도출

큐를 이용한 접근 방식은 단순하다.

1. 1에서 N까지의 수를 큐에 삽입한다.
2. K-1번째 수까지는 첫 번째 값을 맨 뒤로 보낸다.
3. K번째 수일 경우, 큐에서 추출하여 출력한다.
4. 2-3번 과정을 큐의 사이즈가 1개일 때까지 반복한다.
5. 마지막 남은 1개의 원소를 출력한다.

위 아이디어대로 큐를 이용해 구현하면 쉽게 풀 수 있는 문제였다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
                
                StringTokenizer st = new StringTokenizer(br.readLine());
                int N = Integer.parseInt(st.nextToken());
                int K = Integer.parseInt(st.nextToken());

                StringBuilder sb = new StringBuilder();
                sb.append("<");

                // 1. 1부터 N-1까지 큐에 삽입한다.
                // 2. K-1번째 까지는 큐의 첫째 값을 맨 뒤로 보낸다.
                // 3. K번째에는 삽입하여 출력한다.

                Queue<Integer> q = new LinkedList<>();
                for(int i=1; i<=N; i++) {
                    q.offer(i);
                }

                /**
                 * 큐의 원소가 1개 남을 때까지 반복한다.
                 * K-1번째까지는 첫 원소를 맨 뒤로 보낸다.
                 * K번째 값은 추출하여 출력한다.
                 */
                int idx = 1;
                while(q.size() != 1) {
                    if(idx == K) {
                        sb.append(q.poll()+ ", ");
                        idx = 1;
                        continue;
                    }
                    int first = q.poll();
                    q.offer(first);
                    idx++;
                }
                sb.append(q.poll() +">");
                bw.write(sb+"\n");
                
        }
    }    
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.