[백준 알고리즘][자바] 1158번 : 요세푸스 문제

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

1158번: 요세푸스 문제

문제에 분명 "1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고" 라고 순환되는 LinkedList 계열이라고 힌트를 줬는데 배열 형식으로 문제를 해결하려다 보니 시간을 많이 잡아먹게 되었습니다...

 

처음에는 아래의 코드를 ArrayList로 제출을 했더니 시간초과가 나서 혹시나 싶어서 LinkedList로 변경하여 제출했는데

아슬아슬하게 통과했습니다.

 

아마도 데이터 추가와 삭제가 일어날때,

ArrayList는 데이터가 Shift 되면서 더 시간을 잡아먹어서 그런게 아닐까라고 생각해 봅니다.

 

또한 이렇게 문제를 해결하고 다른 분들의 코드를 보니 Queue로 해결하는 것을 알 수 있었습니다.

제가 작성한 코드가 선입선출을 따르긴 하지만요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Number_1158 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] NK = br.readLine().split(" ");
		int N = Integer.parseInt(NK[0]);
		int K = Integer.parseInt(NK[1]);
		
		LinkedList<Object> numList = new LinkedList<>();
		for(int i = 1 ; i <= N ; i++) {
			numList.add(i);
		}

		bw.write("<");
		while (!numList.isEmpty()) {
			for(int i = 0 ; i < K ; i++) {
				if(i != K - 1) { // K번쨰가 아니면
					numList.add(numList.remove(0)); // 앞에서 제거 후 뒤에 다시 추가
				}else {
					if(numList.size() == 1) {
						bw.write(String.valueOf(numList.get(0)));
					}else {
						bw.write(String.valueOf(numList.get(0) + ", "));
					}
					numList.remove(0);
				}
			}
		}
		bw.write(">");
		
		br.close();
		bw.flush();
		bw.close();
	}

}