[백준 / Java] 1168번: 요세푸스 문제 2 (플래티넘 3)

문제 풀이 날짜: 2023.08.08
포스트 작성일: 2023.08.08

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1168번: 요세푸스 문제 2 (플래티넘 3)

 

키워드

구간 합, 세그먼트 트리

 

풀이 접근법

• 세그먼트 트리에 담는 값은 앞으로 뽑아야 할 개수이다.
• 세그먼트 트리의 자식 노드에는 앞으로 뽑아야 할 개수의 부분합을 넣는다. 루트노드가 7이라면 자식 노드로 4와 3을 가진다. (7 = 4 + 3) 
• 부분합 노드를 따라가면 해당 구간에 몇부터 몇까지의 수가 위치해 있는지 알 수 있다. 
  • 예를 들어, 총 7개의 수를 뽑아야 하는 상황에서 3번째 값을 찾고 싶다고 하면, [4] / [3]으로 나뉜 세그먼트 트리에서 4 노드를 선택한다. 3번째 값은 {1, 2, 3, 4} / {5, 6, 7} 구간 중에서 전자에 존재하기 때문이다.
  • 만약 왼쪽 구간과 오른쪽 구간의 크기가 같을 때, 즉 {1, 2} / {3, 4} 로 나뉜 노드에서는 {3, 4}쪽을 더 유망하다고 본다.
• K번째 수를 찾는다고 할 때는, K번째 수를 나타내는 인덱스(rank)를 계속 변화시켜야 한다.
  • 가령 3번째 수를 뽑았다면, 그 위치로부터 또 3번째 뒤에 있는 수를 찾아야 하므로 인덱스를 6으로 변화 시켜준다.
  • 그런데 배열의 길이를 넘은 만큼 인덱스를 늘릴 수는 없으므로, 다음과 같이 일정한 규칙에 따라서 인덱스를 조절해주어야 한다.
  • rank = (rank + K - 2) % (N - i - 1) + 1
  • 이 규칙대로 rank를 변화시키고, 매번의 트리 탐색에서 rank번째에 위치한 값을 뽑아 반환한다.
  • rank 번째 값을 찾고 반환 시키는 과정 중, 세그먼트 트리의 원칙에 맞추어 뽑아야 할 개수를 갱신 시킨다.

 

코드

package algo;

import java.io.*;

public class boj1168 {

	private static final int SIZE = 100_000;
	private static int[] tree;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");
		
		int N = Integer.parseInt(temp[0]);
		int K = Integer.parseInt(temp[1]);
		
		tree = new int[4 * SIZE];
		
		init(0, N - 1, 1); //0부터 N - 1까지 부분합을 초기화한다.
		
		int rank = K;
		
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		for(int i = 0; i < N; i++) {
			int result = update(0, N - 1, 1, rank) + 1; 
			sb.append(result);
			
			if(i < N - 1) {
				rank = (rank + K - 2) % (N - i - 1) + 1;
				sb.append(", ");
			}
		}
		sb.append(">");
		
		System.out.println(sb);
	}
	
	private static int init(int start, int end, int node) {
		if(start == end) {
			return tree[node] = 1; //노드값으로 시작점을 달아준다.
		}
		int mid = (start + end) / 2; //이분 탐색
		return tree[node] 
				= init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
	}
	
	private static int update(int start, int end, int node, int rank) {
		if(start == end) {
			tree[node] -= 1;
			return start;
		}
		
		int mid = (start + end) / 2;
		
		int result = 0;
		if(rank <= tree[node * 2]) { //rank가 왼쪽 자식 노드보다 작거나 같다면
			result = update(start, mid, node * 2, rank); //왼쪽 서브트리 탐색
		} else { //rank > tree[node * 2] //오른쪽 서브트리 탐색
			result = update(mid + 1, end, node * 2 + 1, rank - tree[node * 2]);
		}
		
		/**
		 * 1씩 줄어든 리프 노드를 토대로 윗 부분을 갱신한다.
		 */
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
		
		return result;
	}

}

---

세그먼트 트리는 시간을 O(logN)까지 줄이기 위한 수단에 가깝고, 다음 인덱스(rank)를 잘 구하는 것이 특히 중요한 문제였다. 인덱스 규칙만 잘 찾으면 LinkedList로도 풀 수 있어 보인다. 세그먼트 트리의 내용물로 구간을 저장하는 것까지는 구상해냈으나, 인덱스 계산에서 막혀 다른 풀이를 참고했다.

 

참고 링크

https://byeo.tistory.com/entry/boj-1168-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C-2

 

git 링크

(git 링크 첨부)