백준 11866 요세푸스 With Queue of JAVA

 

---

 

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

11866번: 요세푸스 문제 0

 

---

 

 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        Queue<Integer> q = new LinkedList<>();
        
        int N = in.nextInt();
        int K = in.nextInt();
        
        
        for(int i = 1; i <= N; i++) {
            q.add(i);
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append('<');
        
        
        while(q.size() > 1) {
            
            for(int i = 0; i < K - 1; i++) {
                int val = q.poll();
                q.offer(val);
            }
            
            sb.append(q.poll()).append(", ");
        }
 
        
        sb.append(q.poll()).append('>');
        System.out.println(sb);
    }
 
}

 

 

---

 

먼저 이번에는 스캐너를 통해 만들어보도록 하겠다. 스캐너와 큐를 하나씩 선언해준다. 큐는 스택과 다르게 선입선출 방식으로 제일 먼저 들어온 것이 제일 먼저 나가는 형태를 가지고 있다. 그 다음 스캐너를 통해서 N명의 사람과 제거할 사람의 번호인 K를 입력 받는다. 

 

for문을 사람 수만큼 돌면서 큐에 N만큼의 숫자를 입력한다. 그 다음 StringBuider를 하나 선언해준다.

 

그 다음 sb에 '<'를 추가해준다. 왜냐면 이것도  출력을 해야하기 때문이다.

 

그 다음 포인트로 들어가 보겠다. 

 

        while(q.size() > 1) {
            
            for(int i = 0; i < K - 1; i++) {
                int val = q.poll();
                q.offer(val);
            }
            
            sb.append(q.poll()).append(", ");
        }
 

 

이 부분은 q에 원소가 2개 이상이면 작동하게 되어 있다. 그 다음 for문을 돌면서 0부터 K -1번까지 반복을 한다.

이게 무슨 코드냐면 일단 for문은 큐에 맨 앞에 있는 번호들을 일단 뒤로 이동시킨다. 큐 구조상 맨 앞에 있는 것을 삭제해야 하기 때문이다. 그 다음 그 과정이 완료가 되면 다시 큐에서 맨 앞에있는 숫자를 뽑아서 우리가 출력할 sb에 추가해준다.사이사이가 ","로 나누어져 있기 때문에 이것도 추가해준다. 그 다음 괄호를 스트링 빌더에 넣어주고 그것을 출력하면 된다. 

 

round 1

   loop 1 : {1, 2, 3, 4, 5, 6, 7}  → {2, 3, 4, 5, 6, 7, 1} 

   loop 2 : {2, 3, 4, 5, 6, 7, 1}  → {3, 4, 5, 6, 7, 1, 2} 

   loop 3 : {3, 4, 5, 6, 7, 1, 2}  → 3 출력

 

round 2

   loop 1 : {4, 5, 6, 7, 1, 2}  → {5, 6, 7, 1, 2, 4} 

   loop 2 : {5, 6, 7, 1, 2, 4}  → {6, 7, 1, 2, 4, 5} 

   loop 3 : {6, 7, 1, 2, 4, 5}  → 6 출력

 

round 3

   loop 1 : {7, 1, 2, 4, 5}  → {1, 2, 4, 5, 7} 

   loop 2 : {1, 2, 4, 5, 7}  → {2, 4, 5, 7, 1} 

   loop 3 : {2, 4, 5, 7, 1}  → 2 출력

 

round 4

   loop 1 : {4, 5, 7, 1}  → {5, 7, 1, 4} 

   loop 2 : {5, 7, 1, 4}  → {7, 1, 4, 5} 

   loop 3 : {7, 1, 4, 5}  → 7 출력

 

round 5

   loop 1 : {1, 4, 5}  → {4, 5, 1} 

   loop 2 : {4, 5, 1}  → {5, 1, 4} 

   loop 3 : {5, 1, 4}  → 5 출력

 

round 6

   loop 1 : {1, 4}  → {4, 1} 

   loop 2 : {4, 1}  → {1, 4} 

   loop 3 : {1, 4}  → 1 출력

 

round 7

   loop 1 : {4}  → {4} 

   loop 2 : {4}  → {4}

   loop 3 : {4}  → 4 출력

 

이런 형태로 작동하는 것이다.