[백준] 알고리즘 분류(자료구조,JAVA)1158번, 요세푸스 문제

문제 링크

1158번: 요세푸스 문제

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N명이 원을 이루고 있으며 순서대로 K번째 사람들을 제거한다.

2. 모든 인원이 제거될 때까지 계속된다.

3. 인원이 제거되는 순서를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. List를 이용하여 K번째 사람을 제거합니다.

 

3. 제거되는 모든 순서를 결과로 출력합니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 7

 

K : 3

 

 

2. List를 이용하여 K번째 사람을 제거합니다.

 

1 ~ N번 사람들 List에 구성.

1

2

3

4

5

6

7

 

제거 시작!

 

현재 위치 : 0

제거 위치 : 0 + K = 0 + 3 = 3

 

1

2

4

5

6

7

제거된 사람 : 3번

 

현재 위치 : 2

제거 위치 : 2 + K = 2 + 3 = 5

 

1

2

4

5

7

제거된 사람 : 6번

 

현재 위치 : 4

제거 위치 : 4 + K = 4 + 3 = 7

7 > 5(List.size)으로 첫 위치로 돌아가면서 탐색!

7 % 5 = 2

 

1

4

5

7

제거된 사람 : 2번

 

현재 위치 : 1

제거 위치 : 1 + K = 1 + 3 = 4

 

1

4

5

제거된 사람 : 7번

 

현재 위치 : 3

제거 위치 : 3 + K = 3 + 3 = 6

6 > 3(List.size)으로 첫 위치로 돌아가면서 탐색!

6 % 3 = 3

 

1

4

제거된 사람 : 5번

 

현재 위치 : 2

제거 위치 : 2 + K = 2 + 3 = 5

5 > 2(List.size)으로 첫 위치로 돌아가면서 탐색!

5 % 2 = 1

 

4

제거된 사람 : 1번

 

마지막 남은 4번 사람 제거!

 

3. 제거되는 모든 순서를 결과로 출력합니다.

 

순서 : 3 → 6 → 2 → 7 → 5 → 1 → 4

 

<3, 6, 2, 7, 5, 1, 4>을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 N과 K를 띄어쓰기 기준 나누었습니다.
• K번째 사람들을 순서대로 제거를 진행하며 제거된 사람의 번호를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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


public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList<Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //1 ~ N번 사람 저장
        for(int i=1;i<=N;i++)
            list.add(i);
        bw.write("<");
        int index = 0;	//현재 위치 변수
        while(list.size() > 1){
            //K를 더하였을 때 현재 인원수보다 커질 경우.
            //원형으로 앉아서 처음 인원으로 돌아간다.
            index = index + (K-1) < list.size() ? index + (K-1) : (index + (K-1))%list.size();
            bw.write(list.get(index) + ", ");	//제거된 사람 BufferedWiter 저장
            list.remove(index);		//사람 제거
        }
        bw.write(list.get(0) + ">");		//마지막 남은 사람 BufferedWriter 저장
        bw.flush();			//결과 출력
        bw.close();
        br.close();

    }
}