문제
N명이 1번부터 N번까지 번호를 가지고 줄을 서려고 한다. 원래의 줄 순서는 임의의 순열이다. M개의 조건이 주어지는데, 각 조건은 "i번 사람은 j번 사람보다 앞에 서야 한다"는 형태이다. 주어진 조건을 모두 만족하는 줄 순서를 구하거나, 불가능하면 -1을 출력한다.
단, 이 문제에서는 좀 더 특수한 상황으로 각 조건 (a, b)에 대해 a번 사람의 위치 값을 1 증가시키고 b번 사람의 위치 값을 1 감소시키는 방식으로 풀 수 있다. 초기에 각 사람의 위치 값을 자신의 번호 i로 설정하고, 조건에 따라 값을 조정하여 최종 배치를 만든다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 0 ≤ M ≤ 100,000)
다음 M개의 줄에 i와 j가 주어진다. i번 사람이 j번 사람보다 앞에 서야 한다는 의미이다.
출력
조건을 모두 만족하는 줄 순서를 출력한다. 불가능하면 -1을 출력한다.
예제
입력
5 3
1 3
2 4
3 5출력
1 2 3 4 5풀이
핵심 아이디어: 각 사람 i의 초기 위치 값을 i로 설정한 뒤, 조건 (a, b)마다 a의 값을 +1, b의 값을 -1 조정한다. 최종적으로 각 사람의 값이 유효한 순열(1~N이 각각 한 번씩)이면 그것이 정답이고, 중복이 생기면 -1이다.
- 초기화:
arr[i] = i(1-indexed)로 설정한다. - 조건 반영: 각 조건 (a, b)에 대해
arr[a]++,arr[b]--를 수행한다. - 유효성 검사: 최종
arr[i]값들이 1~N 범위 내에서 중복 없이 존재하는지 확인한다.- 이미 표시된 위치가 나타나면 -1 출력 후 종료한다.
- 출력: 모든 값이 유효하면 순서대로 출력한다.
이 방법이 동작하는 이유는 조건 (a, b)가 a가 b보다 앞에 서야 한다는 것을 의미하므로, a의 위치를 하나 앞으로(값 증가), b의 위치를 하나 뒤로(값 감소) 밀면 상대적 순서가 맞게 조정되기 때문이다.
코드
package day349;
import java.io.*;
import java.util.*;
public class Day340BOJ14864줄서기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
boolean[] sw = new boolean[N + 1];
int[] arr = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
arr[Integer.parseInt(st.nextToken())]++;
arr[Integer.parseInt(st.nextToken())]--;
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
arr[i] += i;
if (sw[arr[i]]) {
System.out.print(-1);
return;
}
sw[arr[i]] = true;
sb.append(arr[i]).append(" ");
}
System.out.print(sb);
br.close();
}
}복잡도
- 시간: O(N + M) — 조건 M개 처리 + N개 순열 검사
- 공간: O(N) —
arr[],sw[]배열