[BOJ] 백준 1849번 순열 (Java)

#1849 순열

난이도 : 플레 5

유형 : 세그먼트 트리

1849번: 순열

▸ 문제

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라.

▸ 입력

첫째 줄에 수열 원소의 개수 (1 ≤ N ≤100,000)이 주어진다. 그리고 두 번째 줄부터 N+1 번째 줄까지 차례로 A[i]가 주어진다.

▸ 출력

N개의 줄에 걸쳐서 수열을 출력한다. (i번째 줄에는 i번째 원소를 의미한다)

 

문제 풀이  

K번째 수를 찾는 유형과 비슷하다. 현재 N칸의 공간 중  앞에 있는 큰 수들을 개수만큼 이미 채워져있는 칸을 제외하고 건너뛰어서 위치를 지정해주면 된다. 예제는 다음과 같이 위치를 배정받게 된다.

수 배정방식

 

 

그런데 자신보다 큰수를 카운트하는 데 선형탐색으로 하면 O(n^2)으로 시간초과가 발생하기 떄문에 트리구조를 사용하여 로그시간으로 줄여줘야 한다. 그래서 세그먼트 트리를 사용하는 것이다. 만약 앞에 자신보다 큰 수가 k개있다고 할 때, 인덱스 트리로 다음과 같이 탐색할 수 있다.

• tree[node*2] > k,  왼쪽 자식 트리가 k보다 크므로 자신보다 작은 값이 나올 때까지 계속 왼쪽 노드로 재귀탐색한다.
• tree[node*2] < k, 왼쪽 자식 트리가 k보다 작으므로 자신보다 작은 개수를 빼주고 (cnt-tree[node*2]) 오른쪽 트리를 재귀 탐색한다.

각 인덱스에 1을 채워놓아서 채워져있는지 비워있는지에 대한 표시를 해준다. 1이면 비어있는 것이다.

 

세그먼트 트리 초기화

 

 

1번 앞에 5개의 큰 수가 있을 경우 다음과 같이 탐색을 하게된다. 

 

 

 

풀이 코드 

import java.io.*;

public class Main {

	static int n;
	static int[] tree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		tree = new int[4*n];
		init(1,n,1);
		
		int[] res = new int[n+1];
		for(int i=1; i<=n; i++) {
			int x = query(1,n,1,Integer.parseInt(br.readLine()));
			res[x] = i;
			update(1,n,1,x);
		}
		
        StringBuilder sb = new StringBuilder();
		for(int i=1; i<=n; i++) {
			sb.append(res[i]+"\n");
		}
		System.out.println(sb.toString());
	}
	
	static void init(int s, int e, int node) {
		if(s == e) {
			tree[node] = 1;
			return;
		}
		
		int mid = (s+e)/2;
		init(s, mid, node*2);
		init(mid+1, e, node*2+1);
		tree[node] = tree[node*2] + tree[node*2+1]; 
	}
	
	static void update(int s, int e, int node, int idx) {
		if(idx < s || e < idx ) return;
		if(s == e) {
			tree[node] = 0;
			return;
		}
		int mid = (s+e)/2;
		update(s, mid, node*2, idx);
		update(mid+1, e, node*2+1, idx);
		tree[node] -= 1;
	}
	
	static int query(int s, int e, int node, int val) {
		if(s == e) return s;
	
		int mid = (s+e)/2;
		if(tree[node*2] > val) {
			return query(s, mid, node*2, val);
		} else {
			return query(mid+1, e, node*2+1, val - tree[node*2]);	
		}
	}	
}