백준 순열(1849)

순열

1. 힌트

1) $A[1]$ 은 1보다 앞에 있는 수 중 $1$보다 큰 수의 개수이다. 그런데 $1$이 가장 작은 수니까 나머지는 모두 $1$보다 크다. 즉, $A[1]$ + 1은 $1$의 위치가 된다.

2) 그렇다면 $x$의 위치는 $A[x] + 1$일까? $1$은 수열에서 가장 작은 원소였기 때문에 성립했던 것이다.

3) $x$의 위치는 자기보다 큰 수의 개수가 $A[x]$개가 되는 위치가 된다. 자기보다 큰 수의 개수는 prefix Sum으로 저장 가능하지만, $A[x]$를 확인하고 나면 $A[x + 1]$에서는 $x$를 없애야하므로 update가 필요하다. 구간 합 세그먼트 트리를 사용한다.

2. 접근

1) 수식으로 표현할 수 있을까?

예제를 직접 손으로 해보니 $A[1] + 1$은 $1$의 위치가 되는 것 같다. $A[2] + 1$도 $2$의 위치가 되는 걸까? 우연히도 예제 입력에서 여기까지는 성립한다. 그러나 $A[3]$부터는 통하지 않는데, 본래 수열을 $S$라고 할 때, $A[3] + 1$은 $2$인데 예제 출력을 보니 $S[2]$에는 $7$이 있다.
이는 $A[x]$에서 $x$보다 왼쪽에 있는게 모두 $x$보다 크다고 생각했기 때문이다.

2) 순서를 강제할 수 있을까?

만약 작은 수부터 순서대로 순회하고, 순회하면서 차례대로 $i$번째 수를 제거한다면 순회중에 $i$번째 수는 언제나 가장 작은 수가 된다. prefix Sum으로 나타내면 자기보다 왼쪽에 있는 수의 개수를 알 수 있지만 update가 있으므로 구간 합 세그먼트 트리를 사용해준다. prefix Sum배열은 단조증가 하므로 이분 탐색이 가능하므로 자기보다 왼쪽에 있는 수의 개수가 $A[i]$개인 지점을 찾아주자.

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		FenwickTree t = new FenwickTree(N);
		for (int i = 1; i <= N; i++) t.add(i, 1);
		int[] S = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			int k = t.kth(Integer.parseInt(br.readLine()) + 1);
			S[k] = i; t.add(k, -1);
		}
		for (int i = 1; i <= N; i++) bw.append(S[i]).append("\n");
		System.out.print(bw);
	}
	
}
class FenwickTree {
	int[] tree;
	
	FenwickTree(int n) { tree = new int[n + 1]; }
	
	void add(int pos, int val) {
		while (pos < tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
	
	int sum(int pos) {
		int ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos -= (pos & -pos);
		}
		return ret;
	}
	
	int kth(int k) {
		int lo = 0; int hi = tree.length - 1;
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if (mid != 0 && sum(mid) >= k) hi = mid;
			else lo = mid;
		}
		return hi;
	}
	
}

1) 시간 복잡도

2) 테스트 케이스