JAVA 알고리즘 : 독캔디를 먹는 죄수 찾기

스터디사이트 : https://www.hackerrank.com

JAVA 알고리즘 : 독캔디를 먹는 죄수 찾기

※ 코딩실습 - 조건

교도소장은 죄수들을 번호 오름차순으로 원형으로 앉혀 놓았다.

그 후 무작위로 처음 캔디를 나눠줄 죄수번호를 정한 뒤에, 번호대로 차례대로 나눠준다. 

( 2를 무작위로 뽑았다면 S=2가 되고, 2,3,4,5 ... , n , 1,2,3,4 ... 로 나눠준다 )

M개의 캔디가 다 떨어질 때까지 죄수들에게 나눠준다.

맨 마지막 캔디는 독이 들어있는데,

독을 먹게 될 죄수는 누가 될 것인지 그 죄수번호를 맞춰 보아라.

1 <= T <= 100  : 테스트 케이스 수

1 <= N <= 10^9 : 죄수들 인원수

1 <= M <= 10^9 : 캔디 갯수

1 <= S <= 10^9 : 처음으로 캔디를 받는 죄수의 죄수번호

입력

1                                                ← 테스트 케이스 수

5 2 1                                           ← N M S

출력

2

디버깅을 이제 본격적으로 해야 할 때가 왔다..

디버깅

캔디가 다 소진되었을 때 ( M=0 )의 죄수번호는 2번이다. 그래서 결과가 2가 나온 것이다.

캔디가 2개인 상태에서 죄수 1번에게 나눠주면, 캔디는 1개가 남게 된다.

그래서 디버깅할 때 나눠준 죄수번호와 나눠준 이후에 남게된 캔디의 개수를 같은 한 줄에 정렬시켜놨다.

디버깅하는 것은 개인 스타일대로 하는 것이라서 나의 스타일대로 정렬 해 보았다.

반복사이클	T (케이스)	N (인원)	M (캔디)	S (시작번호)
0 (초기값)	1	5	2	1
1			1	1
2			0	2

코딩연습-1 & 결과

위의 디버깅 표에 있는 각 변수들은

본인이 반복문으로 써먹게 되었을 때 영향을 미치므로,

무작위로 고른 시작 죄수번호 변수( s )를 ppl 이란 변수로 copy하여 지지고 볶을 것이고,

캔디 갯수 ( m ) 를 candies란 변수로 copy하여 지지고 볶을 것이다.

아래 코딩과 결과를 보면 이해가 갈 것이다.

public static void main(String[] args) {         /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */         Scanner scan = new Scanner(System.in);         int t=scan.nextInt();  // number of test cases                  int n;  // number of prisoners         int m;  // number of sweets         int s;  // prisoner ID   System.out.printf("t : %d , n : %d , m : %d , s : %d\n", t, n, m, s);         int ppl; // prisoner ID 계산을 위한 사본 변수         int candies; // 캔디 계산을 위한 사본 변수                  // test case만큼 반복         for(int i=0; i<t; i++){  n=scan.nextInt();  // number of prisoners             m=scan.nextInt();  // number of sweets             s=scan.nextInt();  // prisoner ID             ppl = s-1;             candies = m;             // 죄수id 무작위로 시작해서 캔디 다 소진할 때까지 반복             for(int j=s; j < s+candies ; j++){                 if(ppl == n){   // ppl이 입력된 입력된 사람수 n을 넘어가게 되면 0으로 초기화                     ppl=0;                 }                 if(m > 0){                     m--;        // m = m - 1                     ppl++;     // ppl = ppl + 1                 }                 System.out.printf("m : %d ppl : %d\n", m, ppl);             } //end for         }         System.out.println(ppl);     } //end main()

결과 :  t : 1 , n : 5 , m : 2 , s : 1 m : 1 ppl : 1 m : 0 ppl : 2 2

코딩결과

public static void main(String[] args) {         /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */         Scanner scan = new Scanner(System.in);         int t=scan.nextInt();  // number of test cases                  int n;  // number of prisoners         int m;  // number of sweets         int s;  // prisoner ID         int ppl;       // prisoner ID 계산을 위한 사본 변수         int candies;  // 캔디 계산을 위한 사본 변수                  // test case만큼 반복         for(int i=1; i<=t; i++){             n=scan.nextInt();  // number of prisoners             m=scan.nextInt();  // number of sweets             s=scan.nextInt();  // prisoner ID             ppl = s-1;             candies = m;                          // 죄수id 무작위로 시작해서 캔디 다 소진할 때까지 반복             for(int j=s; j < s+candies; j++){                 if(ppl == n){   // ppl이 입력된 사람수 n을 넘어가게 되면 0으로 초기화                     ppl=0;                 }                 if(m > 0){                     m--;                     ppl++;                 }             } //end for n m s             System.out.println(ppl);         } //end for test case } // end main()

결과 :  2

다른 사람의 간단한 코딩.

public static void main(String[] args) { Scanner sc=new Scanner(System.in); long t=sc.nextLong(); for(int i=0;i<t;i++){ long noOfprisoner=sc.nextLong(); long noOfSweet=sc.nextLong(); long startId=sc.nextLong()-1; long result=(startId+noOfSweet-1)% noOfprisoner; /*long result = (noOfSweet % noOfprisoner) + startId; result = result % 5;*/ if(result ==0){ System.out.println(noOfprisoner); }else{ System.out.println(result); } //end if } //end for }

결과 :  2