[백준] 1158번 : 요세푸스 문제

문제

n명의 사람이 원을 그리며 앉아 있을 때 k번째 사람을 한 명씩 빼주는 문제로

리스트를 계속 돌아야 한다.

 

접근 방식

7명의 사람이 원을 그리며 앉아 있을 때

진행 과정은 아래와 같다.

 

1, 2, 3, 4, 5, 6, 7

1, 2, 4, 5, 6, 7

1, 2, 4, 5, 7

1, 4, 5, 7

1, 4, 5

1, 4

4

 

결과는 <3, 6, 2, 7, 5, 1, 4> 라는 순열이 만들어 진다.

 

결국 1부터 n번째 사람이 모두 빠질 때까지 반복문을 돌면서

빠지는 순서대로 출력 버퍼에 추가해주면 된다.

 

문제가 하나 있는데 리스트의 끝까지 왔다면 다시 처음으로 돌아가야 한다.

이터레이터는 전후 한 칸 이동만 가능하기 때문에 처음으로 갈 수가 없다.

 

iterator = list.listIterator();
iterator = list.listIterator(0);

 

이터레이터를 초기화 하면 항상 0번째 인덱스부터 시작하고

특정 인덱스부터 시작하고 싶은 경우에는 해당 인덱스 번호를 파라미터로 주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		bw.write("<");

		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);

		LinkedList<Integer> list = new LinkedList<>();

		for (int i = 1; i <= n; i++) {
			list.add(i);
		}

		ListIterator<Integer> iterator = list.listIterator();

		int cur = 0;

		while (!list.isEmpty()) {
			if (list.size() == 1){
				bw.write(list.get(0) + "");
				list.remove(0);
			}
			else {
				for (int i = 0; i < k; i++) {
					if (iterator.hasNext()) {
						cur = iterator.next();
					} else {
						iterator = list.listIterator();
						cur = iterator.next();
					}

					if (i == k - 1 && list.size() > 1) {
						bw.write(cur + ", ");
						iterator.remove();
					}
				}
			}

		}

		bw.write(">");
		bw.flush();
		bw.close();
	}
}

 

자바에서 LinkedList는 Queue의 구현 클래스이기도 해서

나중에 이 문제를 다시 큐를 사용해서 풀어보겠다.