[백준(BOJ)] 1158번 : 요네푸스 문제 - JAVA[자바]

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 큐

 

---

 

⊙ 문제 접근 과정

 

Queue를 이용해 접근했다. 문제에서 원하는 건 N명의 사람을 입력받은 후, K번째마다 추출하고 String에 계속하여 추가해주면 되는 문제다. String을 계속해서 수정해주어야 하기 때문에 StringBuilder를 선언해주었다.

 

만약 N=5 , K= 2이면

 

1.    {1,2,3,4,5}

2.-> {2,3,4,5,1}  ☞ 2번째 제일 앞 숫자(2) 추출

 

3.-> {3,4,5,1}

4.-> {4,5,1,3}    ☞ 2번째 제일 앞 숫자(4) 추출

 

5.-> {5,1,3}

6.-> {1,3,5}      ☞ 2번째 제일 앞 숫자(1) 추출

 

7.-> {3,5}

8.-> {5,3}        ☞ 2번째 제일 앞 숫자(5) 추출

 

9.-> {3}

10.->{3}         ☞ 2번째 제일 앞 숫자(3) 추출

 

결과는 이렇게 나온다.

 

이제 이 순환성을 잡아 구현하기만 하면 된다.

---

 

⊙ Queue

 

• Queue란?

       Queue는 First In First Out의 형태이다. (FIFO)

       먼저 들어온 데이터가 먼저 나가는 형태인데 줄 서는 것을 생각하면 된다.

       Queue의 형태는 인터페이스 형태로 LinkedList를 통해 생성된다.

 

• Queue 사용법

       Queue와 LinkedList가 전부 import 되어 있어야 사용이 가능하다.

 

queue.add(1)	queue에 1이란 값 추가
queue.offer(1)	queue에 1이란 값 추가
queue.poll()	queue에 첫번째 값 반환
queue.peek()	queue에 첫번째 값 참조
queue.remove()	queue 첫번째 값 제거
queue.clear()	queue 초기화

 

 

---

 

⊙ 문제 풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        //queue를 선언한다.
        Queue<Integer> q = new LinkedList<>();

        int N = in.nextInt();
        int K = in.nextInt();

        //N번까지 queue에 추가.
        for(int i =1;i<=N;i++) {
            q.add(i);
        }

        //String을 계속 추가, 수정해야하므로 StringBuilder 선언 !
        StringBuilder people = new StringBuilder();
        people.append('<');

        //queue에서 다 뽑을 때까지 계속 돌린다.
        while (q.size()>1) {

            //K의 배수가 아닌 값은 뽑고 다시 넣는다.
            for(int i =0; i<K-1;i++) {
                int value = q.poll();
                q.offer(value);
            }
            //뽑은 값을 String에 추가
            people.append(q.poll()).append(", ");
        }

        //마지막에 '>'로 닫아주고 출력
        people.append(q.poll()).append('>');
        System.out.println(people);
    }
}

 

 

 

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

큐를 이해하여 문제에 정확히 활용하여 적용해보자.