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
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 12757] 전설의 JBNU (java) (0) | 2024.04.12 |
---|---|
[백준, BOJ 19535] ㄷㄷㄷㅈ (java) (0) | 2024.04.11 |
[백준, BOJ 18223] 민준이와 마산 그리고 건우 (java) (0) | 2024.04.08 |
[백준, BOJ 9084] 동전 (java) (0) | 2024.04.07 |
[백준, BOJ 2900] 프로그램 (java) (0) | 2024.04.07 |