[인프런 알고리즘 문제풀이] 공주 구하기

문제

인프런 알고리즘 문제풀이

• The copyright in this matter is in Inflearn

입력

8 3

출력

7

풀이

이 문제는 조세퍼스 관련 문제이며 n과 k가 주어질 때, 1번부터 n번까지의 왕자가 시계방향으로 돌아가며 동그랗게 앉게한 다음,
1번 왕자부터 시계방향으로 돌아가며 1투터 시작하여 번호를 외치게 한다. 한 왕자가 k를 외치면
그 왕자는 제외되고 다시 다음 왕자부터 1부터 시작하여 번호를 외친다. 이렇게해서 마지막까지 남은
왕자의 번호를 출력한다.

n = 8과 k = 3이 주어진 경우

1 2 3 4 5 6 7 8

1 2 4 5 6 7 8

1 2 4 5 7 8

2 4 5 7 8

2 4 7 8

4 7 8

4 7

7

위 순서로 왕자가 제외되고 마지막까지 남은 7번 왕자가 답이 된다.

코드에서는 우선,
1. p라는 1차원 배열을 모두 0으로 초기화한다.
2. 현재 위치를 나타내는 pos라는 변수를 이용하여 1번왕자부터 탐색하고 번호를 외치는 것을
cnt라는 변수를 이용하여 p 배열의 0의 갯수를 카운팅하여 cnt가 3이 되었을때 그 자리의
배열을 1로 바꿔주고 체크한다. 체크할 때 ansCnt변수에 몇명 카운팅했는지 센다.
그리고 cnt를 다시 0으로 만든 뒤 다시 pos를 움직이며 카운팅.
2-1. 맨 뒤에 왕자가 번호를 외치고 그 후 맨 처음 왕자가 번호를 외쳐야되는
경우가 있으니 현재 위치 pos가 n보다 클 때에는 pos를 1로 바꿔줘야한다.
2-2. 계속 카운팅하다 ansCnt가 n-1일 때 반복문 빠져나오고 현재 위치 pos를 출력
(0번째 인덱스부터 시작하는 것이니 pos-1)

코드

/*45. 공주구하기 (조세퍼스)*/
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        
        System.setIn(new FileInputStream("input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] p = new int[n];

        int pos = 0;
        int cnt = 0;
        int ansCnt = 0;
        while(true){
            pos++;
            if(pos > n){
                pos = 1;
            }
            if(p[pos-1]==0){
                cnt++;
                if(cnt == k){
                    p[pos-1] = 1;
                    cnt = 0;
                    ansCnt++;
                }
            }

            if(ansCnt == n-1){
                break;
            }
            
        }

        for(int i = 0;i<n;i++){
            if(p[i] == 0){                        
                System.out.println(i+1);
                break;
            }
        }
        
    }
}