백준 1158번: 요세푸스 문제

코드: https://github.com/kgh128/Problem-Solving/blob/main/src/Baekjoon/p1158.java

1. 큐 초기 세팅

큐는 원을 이루면서 앉아있는 사람들을 저장하는 공간이다. 가장 처음에는 N명의 사람이 모두 앉아있으므로 1~N을 큐에 순서대로 저장한다.

Queue<Integer> queue = new LinkedList<>();

for (int i = 1; i < N+1; i++) {
	queue.add(i);
}

자바에서 큐는 아래와 같이 사용할 수 있다. 주의해야 할 점은 큐를 생성할 때 LinkedList를 이용하여 생성해야 한다는 점이다.

import java.util.Queue;
import java.util.LinkedList;

// 1. 생성
Queue<Integer> queue = new LinkedList<>();

// 2. 삽입
queue.add(1);	// 성공: true 반환, 공간이 없어서 실패: 예외 발생
queue.offer(2);	// 성공: true 반환, 공간이 없어서 실패: false

// 3. 가장 앞에 있는 원소를 조회하고 제거
queue.remove();	// 큐가 비어있으면 예외 발생
queue.poll();	// 큐가 비어있으면 null 반환

// 4. 가장 앞에 있는 원소 조회
queue.element();	// 큐가 비어있으면 예외 발생
queue.peek();		// 큐가 비어있으면 null 반환

// 5. 큐가 비어있는지 확인
if (queue.isEmpty()) {}

2. 큐를 순환하면서 K번째 원소 제거

큐의 가장 앞에 있는 원소를 뽑고 count 값을 1 증가시킨다. 해당 원소가 K번째로 뽑은 원소이면 출력 버퍼에 저장하고 몇번째로 뽑았는지를 저장하는 count 값을 0으로 초기화한다. 해당 원소가 K번째로 뽑은 원소가 아니면 그 원소를 다시 큐의 가장 뒤에 삽입한다. 이런식으로 큐가 빌 때까지 순환하면서 K번째 원소를 제거한다.

직관적으로 큐가 원이고, 뽑아서 출력 버퍼에 저장되는 원소가 제거된 사람, 다시 큐에 삽입되는 원소가 아직 제거되지 않고 원에 남은 사람이다. 큐의 First In First Out 성질을 이용하여 원을 따라가는 순서를 유지한다.(순환할 수 있다.) 큐의 가장 앞에 있는 원소가 원을 따라갈 때의 현재 위치이다.

int count = 0;

while (!queue.isEmpty()) {
	int head = queue.poll();
	count++;

	if (count == K) {
		count = 0;
		bw.append(head).append(", ");
	}
	else {
		queue.add(head);
	}
}

3. 결과 출력

2의 while문을 돌면서 ", "를 계속 붙여주므로 마지막 원소 뒤에도 ", "이 붙어있다. 이를 제거하고 ">"를 추가해야 한다. 그러기 위해서 replace(start, end, str) 메소드를 이용한다. 이는 start~end 이전까지의 문자열을 str로 대체하는 메소드이다.

bw.replace(bw.length()-2, bw.length(), ">");
System.out.print(bw);

처음에는 bw.deleteCharAt(bw.length()-1).append(">")'를 해서 틀렸다. ", "는 가장 마지막에 있는 두 원소인데, 위와 같이 하면 가장 뒤에 있는 원소 " "만 삭제되고 ">"가 추가되어 ",>"가 되기 때문이다. ","도 삭제되었어야 하므로 틀렸다.