문제 링크
문제
티어: 골드 2
알고리즘: 그리디, bfs, dfs
입력
첫 번째 줄에 자연수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에 자연수 k와 p(1 ≤ k, p ≤ N)가 공백으로 구분되어 주어진다.
출력
자연수 k가 heap 배열의 p번째에 위치하도록 하는 삽입 순서가 존재한다면 i번째 줄에 i번째로 삽입할 수를 출력한다. 가능한 삽입 순서가 여러 가지라면 그중 아무거나 하나를 출력해도 된다. 만약 그렇게 만드는 삽입 순서가 존재하지 않는다면 첫 번째 줄에 -1을 출력한다.
풀이
삽입 순서를 찾기 위해서 우리는 p번째에 k가 들어간 상황으로 먼저 봐야한다.
heap[p] = k; 에서 p의 모든 조상은 k보다 작은 값을 가지고, p의 모든 하위 트리는 k보다 큰 값을 가진다.
먼저, 조상을 채우는 방법부터 보자.
p의 모든 조상은 k보다 작다고 했다. 이때 k보다 작은 값 중에 어떤 값을 넣어야 할까?
답은 루트부터 p의 부모까지 1, 2... 순으로 넣으면 된다.
왜냐하면 루트는 당연히 1값을 가져야하며, 그 다음 자식은 부모보다 크면서 가장 작은 2값을 가져야 가능성을 최대로 할 수 있다. 즉, 최선의 선택인 것이다.
이렇게 최선의 선택을 했음에도 p의 조상 중 k보다 큰 값을 가지는 노드가 있는 경우 삽입 순서는 존재하지 않기 때문에 -1를 출력한다.
다음 p의 하위 트리를 채우는 방법을 보면
p의 하위 트리는 k보다 큰 값을 가진다. 이때 k보다 큰 값 중 어떤 값을 넣어야 할까?
답은 자식 노드부터 리프 노드까지 k + 1, k + 2... 순으로 넣으면 된다.
왜냐하면 k + 1부터 넣어야지 각 노드의 넣을 수 있는 가능성을 최대로 할 수 있다. 즉, 최선의 선택이다.
예를 들어 k가 5일 때 6부터 넣어야지 8을 넣으면 그 하위 노드는 9부터 넣을 수 있기 때문에 선택지가 좁아지는 것을 볼 수 있다.
이렇게 최선의 선택을 했음에도 p의 하위 노드 중 N보다 큰 값을 가지는 노드가 있는 경우 삽입 순서는 존재하지 않기 때문에 -1를 출력한다.
마지막으로 p의 조상과 하위 트리를 채울 수 있다면, 나머지 노드는 나머지 값으로 순서대로 채우면 된다.
그리디 + bfs + dfs 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
int[] heap = new int[N + 1];
boolean[] visited = new boolean[N + 1];
heap[p] = k;
visited[k] = true;
boolean isPosible = true;
//부모 구성
ArrayList<Integer> parent = fillOrderParent(p); //reverse
int cursorK = 1;
for(int i=parent.size() - 1; i>=0; i--) {
if(cursorK >= k) {
isPosible = false;
break;
}
heap[parent.get(i)] = cursorK;
visited[cursorK] = true;
cursorK += 1;
}
if(!isPosible) {
System.out.println(-1);
return;
}
//자식 구성
ArrayList<Integer> child = fillOrderChild(p);
cursorK = k + 1;
for(int i=0; i<child.size(); i++) {
if(cursorK > N) {
isPosible = false;
break;
}
heap[child.get(i)] = cursorK;
visited[cursorK] = true;
cursorK += 1;
}
if(!isPosible) {
System.out.println(-1);
return;
}
//나머지 구성
cursorK = 1;
for(int i=1; i<=N; i++) {
if(heap[i] == 0) {
while(visited[cursorK]) {
cursorK += 1;
}
heap[i] = cursorK;
visited[cursorK] = true;
}
}
StringBuilder sb = new StringBuilder();
for(int i=1; i<=N; i++) {
sb.append(heap[i]).append("\n");
}
System.out.println(sb.toString().trim());
}
static ArrayList<Integer> fillOrderChild(int p) {
ArrayList<Integer> result = new ArrayList<>();
Queue<Integer> que = new LinkedList<>();
que.add(p);
while(!que.isEmpty()) {
int parent = que.poll();
int leftChild = parent * 2;
if(leftChild <= N) {
result.add(leftChild);
que.add(leftChild);
int rightChild = leftChild + 1;
if(rightChild <= N) {
result.add(rightChild);
que.add(rightChild);
}
}
}
return result;
}
static ArrayList<Integer> fillOrderParent(int p) {
ArrayList<Integer> result = new ArrayList<>();
if(p == 1) {
return result;
}
int nextParent = p / 2;
result.add(nextParent);
while(nextParent != 1) {
nextParent = nextParent / 2;
result.add(nextParent);
}
return result;
}
}