[백준, BOJ 3665] 최종 순위 (java)
Problem Solving/BOJ

[백준, BOJ 3665] 최종 순위 (java)

728x90

https://www.acmicpc.net/problem/3665

 

3665번: 최종 순위

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에

www.acmicpc.net

728x90

메모리: 36,928 KB , 시간: 424  ms

사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 위상 정렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder result = new StringBuilder();
int T = Integer.parseInt(br.readLine());
int n, num, m, a, b;
int[][] arr;
Map<Integer, Integer> map;
StringBuilder tmp;
boolean flag;
for (int tc = 0; tc < T; tc++) {
n = Integer.parseInt(br.readLine());
arr = new int[n + 1][2];
arr[0][0] = n + 1;
map = new HashMap<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
num = Integer.parseInt(st.nextToken());
arr[num][0] = i;
arr[num][1] = num;
map.put(num, i);
}
m = Integer.parseInt(br.readLine());
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
if(map.get(a) < map.get(b)) {
arr[a][0]++;
arr[b][0]--;
}
else {
arr[a][0]--;
arr[b][0]++;
}
}
Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);
tmp = new StringBuilder();
flag = false;
for (int i = 0; i < n; i++) {
if(arr[i][0] != i) {
result.append("IMPOSSIBLE\n");
flag = true;
break;
}
if(i != n - 1) tmp.append(arr[i][1] + " ");
else tmp.append(arr[i][1]);
}
if(!flag) result.append(tmp + "\n");
}
System.out.print(result);
}
}
728x90