[java] 1158 요세푸스

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

1. 큐
2. Arraylist에서 제거될 사람을 한 명씩 remove

배열 복습중이라 2번 방법으로 풀었고, 백준 예시 1로 설명해보겠습니다

노란색 셀 : 현재 제거된 사람 번호
문제 : 7명, 3번째 사람을 순서대로 제거

첫번째 턴 : 3번째 사람 = 3번

두번째 턴 : 3번째 사람 = 6번

• 이전에 제거된 사람 자리부터 3번째이므로 , 6

세번째 턴 : 3번째 사람 = 2번

• 이전에 제거된 사람 자리 (6) 부터 3번째 , 2

네번째 턴 : 이전에 제거된 사람부터 3번째 사람 = 7

여기서 인덱스 값의 변화가 규칙적으로 변함을 알 수 있습니다.
→ i번째 차례에 제거되야 할 사람 : 이전인덱스 + (K-1)
→ K 가 아닌 K-1 을 한 이유 : 현재 자리 포함하여 출발하기 때문에 - 1

해당 예시에서는 K=3 이므로 K-1 = 2 가 됩니다

3번째는 배열의 크기를 벗어나므로 7 - 배열크기를 해줍니다.
배열크기보다 클 때 배열 크기를 빼주는 코드말고 arr.size() 로 나눠서 모든 인덱스에 적용했습니다

if(nowIdx > arr.size()){
	nowIdx = nowIdx - arr.size();
}else{
}

랑

nowIdx = nowIdx%arr.size();

랑 똑같은 값을 도출해냅니다.

어레이 크기보다 클 때 => 1.xx 이므로 나머지 값이 인덱스가 되고
어레이 크기보다 작을 때=> 0.xx 이므로 나머지 값이 인덱스가 되기 때문

따라서 아래 계산식으로 제거인덱스 구함
nowIdx = (nowIdx+K)%arr.size();

3. 코드

import java.io.*;
import java.util.*;
import java.awt.Point ;

public class Main {

	static int N,K,nowIdx;
	static ArrayList<Integer> arr ;

	public static int stoi(String str){
		return Integer.parseInt(str);
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new ArrayList<>();
		N = stoi(st.nextToken()); // N명
		K = stoi(st.nextToken())-1; // K번째 사람 제거

		for(int i=1;i<N+1;i++) arr.add(i); // 1	부터 N까지 채움

		StringBuilder sb = new StringBuilder();
		int count = 0 ;

		sb.append("<");
		while(arr.size() > 1){
			nowIdx = (nowIdx+K)%arr.size();
			sb.append(arr.get(nowIdx) +", ");
			arr.remove(nowIdx);
		}

		sb.append(arr.get(0) + ">");

		System.out.println(sb.toString());
	} 

}