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

🔺 문제

1158번: 요세푸스 문제

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1 ; i <= N ; i++) {
            queue.add(i);
        }
        
        sb.append("<");
        
        // K-1까지 처음에 있던 값을 맨 뒤로 보냄
        while(queue.size() != 1) {
            for(int i = 0 ; i < K - 1 ; i++) { // K번이 아닐 때는 맨 뒤로 이동
               queue.offer(queue.poll());
            }
            sb.append(queue.poll()).append(", "); // K번이 되면 제거
        }
        
        sb.append(queue.poll()).append(">"); // 큐에 남은 마지막 원소
        System.out.println(sb);
    }
}
 

✅ 해결 아이디어
✔ 큐
- 1~N까지 숫자를 넣는다.
- 큐의 첫 번째 원소부터 K-1번째 숫자를 큐에서 빼고 맨 뒤에 추가
- K번째 원소는 큐에서 ㅅ제거
- 큐에 남아있는 원소가 1이 아닐 때까지 반복

 

 

---

🔺 다른 풀이들

- 과정 설명 & 그림 굿ㅠㅠㅠ

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

---

💬 느낀 점

어떻게 큐 쓸 생각을.......ㅎㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	240321

 

 

(+240321 2회독 : 16440KB, 192ms)

인덱스를 활용해서 더 효율적인 방법으로 풀었다! 🤭🤭

큐를 LinkedList로 선언해서 해당 idx의 값을 제거하고 가져올 수 있게 했다.

import java.util.*;
import java.io.*;
 
public class 요세푸스문제_한의정 {
    static int N,K;
    static LinkedList<Integer> q = new LinkedList<>();    // LinkedList로 큐 선언해 인덱스에 위치한 값 제거
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        K = Integer.parseInt(str[1]);
 
        if(N == 1) {    // N이 1이면 바로 처리
            System.out.println("<1>");
            return;
        }
 
        for(int i = 1 ; i <= N ; i++)   q.add(i);
 
        int idx = K-1;
        sb.append("<" + q.remove(idx) + ", ");
 
        while(!q.isEmpty()) {
            idx = (idx + K -1) % q.size();
            int num = q.remove(idx);
 
            sb.append(num);
            if(q.size() != 0)
                sb.append(", ");
        }
 
        sb.append(">");
        System.out.println(sb.toString());
    }
}
 

 

---

(참고)

[백준] 1158번 요세푸스 문제 자바(Java)