[Baekjoon] 17857_Musical Chairs

문제(출처: https://www.acmicpc.net/problem/17857)

---

< Musical Chairs >

 

문제 풀이 

 

ArrayList를 사용하여 새로운 학과장을 뽑는다.

 

* Queue를 사용하여 문제를 해결할 경우 시간 초과가 발생한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class _17857_ { // Musical Chairs

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());
		ArrayList<int[]> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(new int[] { i + 1, Integer.parseInt(st.nextToken()) });
		}

		int idx=0;
		while (list.size() != 1) {
			idx += list.get(idx)[1] % list.size() - 1;
			if (idx < 0) {
				idx = list.size() - 1;
			}else if(idx >= list.size()) {
				idx-=list.size();
			}
			list.remove(idx);
			
			if(idx >= list.size()) {
				idx=0;;
			}
		}
		System.out.println(list.get(0)[0]);
	}
}

변수)
n : 교수 수
list : ArrayList <int []>
idx : 현재 위치

 

교수 수를 입력받는다. 교수 수만큼 번호를 입력받아 ArrayList에 자신의 인덱스와 입력받은 번호를 저장한다. ArrayList의 크기가 1이 아닐 때까지 현재 위치에 있는 교수의 번호를 보고 제거할 교수 index를 구해 제거하는 과정을 반복한다.

 

최종 ArrayList에 있는 교수의 index를 출력한다.

---

---