BOJ 백준 25988 Inked Inscriptions

 

문제 : https://www.acmicpc.net/problem/25988

[ 문제 요약 ]

• 두 개의 책을 갖고 있습니다. 왼쪽 책 내용을 오른쪽 책에 복사할 것입니다. 왼쪽 책 페이지의 내용을 오른쪽 책의 특정 페이지 마다 복해 넣을 것입니다.
• 배열이 주어지고, 그 배열의 인덱스는 원래 페이지(왼쪽 책), 배열의 값들은 복사할 페이지(오른쪽 책) 번호를 의미합니다.
• 책을 복사할 때 두 책을 최소한으로 넘기는 순서를 출력합니다.
• 책을 넘긴 횟수는 최대 2n√ n(소수점 이하 올림)이어야 합니다.

 

[ 테스트 케이스 설명 ]

5		// 시편의 수 (1<=10,000)
4 1 3 5 2	// i번째 정수가 j라면, i 페이지에 있는 시편을 새로운 책의 j페이지에 복사해야 함을 의미
// 답 : 기존 책의 i페이지에 있는 시편을 새로운 책의 j페이지에 복사 해야 함을 출력
2 1
3 3
5 2
4 5
1 4

 

[ 알고리즘 분류 ]

• 해 구성하기
• 오프라인 쿼리
• Mo’s 알고리즘

 

[ 문제 해설 ]

 

먼저 두 책을 최소한의 이동으로 복사하는 것을 생각해 보면, 두 책 중 하나는 고정되어 있어야 합니다. 그래야 한 책은 한 장씩 순서대로 넘기면서 복사를 할 수 있기 때문입니다.

 

하나의 책을 고정시킨 후, 나머지 책도 최소한으로 움직여야 합니다. 이를 위해 알고리즘을 사용해 정렬합니다.

 

이 문제는 Mo’s 알고리즘을 알고 있으면 쉽게 풀 수 있습니다.

 

Mo’s 알고리즘은 배열을 sqrt(N) 구간으로 나눠(N은 배열 길이) 포인터의 이동을 최소화하는 알고리즘입니다.

 

sqrt(N) 구간으로 나누면, 구간이 sqrt(N) 개 생기게 되고, 이것을 하나의 블록이라 했을 때, 블록 사이에서 최소한의 이동이 보장되기 때문입니다.

 

같은 구간인 경우, 구간의 수가 짝수일 때는 다른 포인터(여기서는 고정되지 않은 책쪽)를 오름차순정렬하고, 홀수일 때는 내림차순으로 정렬해 포인터 이동이 최소가 되도록 합니다.

 

이렇게 하면 연속한 두 쿼리 사이에서 L 과 R 이 한 번에 멀리 점프하는 일이 거의 사라져, 전체 이동 횟수가 O(2N√ N)에 그치게 됩니다.

 

맨 처음 설명할 때 한 책을 고정시킨다고 했는데, 사실 완전히 한 책의 페이지가 고정되는 게 아니라 차이가 있을 수 있습니다.

 

그러나 구간 안에서 포인터의 이동이 크지 않게 정해져 있기 때문에 큰 차이가 나지 않습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());//시편의 수 (1<=10,000)
		int sqrt = (int)Math.sqrt(N);
		
		ArrayList<Page> page = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int origin=1; origin<=N; origin++)
		{
			int copy = Integer.parseInt(st.nextToken());
			// 원래 페이지와 복사할 위치의 페이지 번호를 넣고, 복사할 위치 페이지 번호를 기준으로 구간을 정합니다.
			page.add(new Page(origin, copy, copy / sqrt));
		}
		
		Collections.sort(page);
		
		StringBuilder sb = new StringBuilder();
		// 출력시 원래 페이지 먼저 출력합니다.
		for(Page p : page)
			sb.append(p.origin).append(' ').append(p.copy).append('\n');

		System.out.print(sb);
	}
	static class Page implements Comparable<Page>{
		int origin, copy, factor;
		Page(int o, int c, int f){
			this.origin = o;
			this.copy = c;
			this.factor = f;
		}
		@Override
		public int compareTo(Page p) {
			// 구간이 동일 하지 않다면 구간 기준 오름차순 정렬
			if(this.factor != p.factor)
				return this.factor - p.factor;

			// 구간이 짝수면 원래 페이지 기준 오름차순 정렬
			if(this.factor % 2 == 0)
				return this.origin - p.origin;
			
			// 구간이 홀수면 원래 페이지 기준 내림차순 정렬
			return p.origin - this.origin;
		}
	}
}