Cooper's devlog

조세퍼스 문제 : 1158번 - JAVA 본문

Algorithm/Baekjoon

조세퍼스 문제 : 1158번 - JAVA

cooper_dev 2020. 7. 8. 17:14

1. 문제 링크

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

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

 

2. 문제 설명

 

 

3. 문제 접근

 

Queue : FIFO(First In First Out) 형태를 띄고 있는 자료구조.

 

예제 입력1 (N = 7, K =3)

 

(1) Queue에 인원 수(N) 만큼의 숫자를 추가한다.

<Queue>

     Front                                                                                                                               Tail

1 2 3 4 5 6 7  

 

 

(2) K번째 사람을 제거하기 위해, K-1만큼 Queue의 출력한 값을 다시 Queue에 추가한다.

     (1) K - 1 = 2 이므로, 1번과 2번을 뽑아서 뒤로 보낸다.(차례대로 하나씩 옮긴다)

 

[이동 전]

<Queue>

     Front                                                                                                                               Tail

1 2 3 4 5 6 7  

 

[이동 후]

<Queue>

     Front                                                                                                                               Tail

3 4 5 6 7 1 2  

 

 

(3) K번째가 되면 답안에 추가한다.

<Queue>

     Front                                                                                                                               Tail

3 4 5 6 7 1 2  

    |

   └------> 뽑아서 답에 추가

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
 
public class Josephus {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Queue<Integer> queue = new LinkedList<>();
        
        String[] testArr = br.readLine().split(" ");
        int people_num = Integer.parseInt(testArr[0]);
        int interval = Integer.parseInt(testArr[1]);
        
        for (int i = 1; i <= people_num ; i++)    queue.add(i);
        
        bw.write("<");
        while(!queue.isEmpty()) {
            for (int i = 1; i < interval; i++) {
                queue.add(queue.poll());
            }
            bw.write(String.valueOf(queue.poll()));
            if(!queue.isEmpty())bw.write(", ");
        }
        
        bw.write(">");
        br.close();
        bw.flush();
        bw.close();
    }
}
 
  

 

5. 개선점 또는 트러블 슈팅

선입선출 또는 원형과 관계된 문제가 출제될 때는 Queue로 접근하는 방식을 먼저 고려하는 것이 효율적일 것이다.

 

'Algorithm > Baekjoon' 카테고리의 다른 글

쇠막대기 :10799번 - JAVA  (0) 2020.07.09
단어 뒤집기 :17413번 - JAVA  (0) 2020.07.09
에디터:1406번 - JAVA  (0) 2020.07.08
스택수열 : 1874번 - JAVA  (0) 2020.07.07
괄호 : 9012번 - JAVA  (0) 2020.07.07
'Algorithm/Baekjoon' Related Articles more
Comments