이코테 - 최종 순위 with JAVA

 

 

문제 

작년 순위가 주어지고 높고 낮음이 뒤바뀐 사람들이 주어진다.

이때, 순위를 정확히 알 수 없다면, ?, 데이터에 문제가 있다면 Impossible, 그렇지 않다면 순위를 출력하라

 

 

 

로직

순위를 정확히 알 수 있는가에 대한 질문으로 위상정렬이 기본적으로 떠오른다.

Base가 되는 구성으로 순위가 낮을 수록 진입 차수가 높아지며 사람들 간 관계를 표현하는 방법으로 graph를 통해 graph[a][b]가 true 이면 a가 b보다 순위가 높음을 표현할 수 있다.

 

위의 방법으로 위상정렬을 구현하면

진입차수가 0인 사람을 꺼내면 그 사람이 우선적으로 1등이 되고

그 사람과 연결된 사람들 즉, 그 사람보다 순위가 뒤에 있던 사람들의 진입차수를 1씩 뺐을 때, 0이 되면 더이상 그 사람 위에는 사람이 없음 즉, 그 사람보다 높은 등수의 사람이 없다는 것을 의미하고 큐에 넣으면서 로직을 진행할 수 있다.

이러한 경우, 만약 큐에 사이즈가 0이라면 데이터에 문제가 있음을 의미하고, 2이상이라면 정확한 순위를 알 수 없음을 의미한다.

 

 

 

 

 

코드

import java.util.*;

// 최종 순위
public class Q5 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 반복 횟수
        int t = sc.nextInt();
        for(int tc=0; tc<t; tc++){
            // 사람 수
            int n = sc.nextInt();
            // 진입 차수
            int[] indegree = new int[n+1];
            // 사람마다 관계 그래프
            boolean[][] graph = new boolean[n+1][n+1];
            // 작년 순위
            List<Integer> lastYear = new ArrayList<>();
            for(int i=0; i<n; i++){
                lastYear.add(sc.nextInt());
            }
            // 작년 순위를 바탕으로 초기화
            for(int i=0; i<n; i++){
                for(int j=i+1; j<n; j++){
                    // graph[a][b]가 true 이면 a가 b보다 순위가 높다.
                    graph[lastYear.get(i)][lastYear.get(j)] = true;
                    // indegree = 자신보다 높은 순위의 사람 수
                    indegree[lastYear.get(j)] += 1;
                }
            }

            // 순위 변동
            int m = sc.nextInt();
            for(int i=0; i<m; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                // 기존에 a가 b보다 순위가 높았다면
                if(graph[a][b]){
                    // b가 a보다 순위가 높다.
                    graph[a][b] = false;
                    graph[b][a] = true;
                    // a보다 순위가 높은 사람 수 증가
                    indegree[a] += 1;
                    // b보다 순위가 높은 사람 수 감소
                    indegree[b] -= 1;
                }
                else{
                    graph[a][b] = true;
                    graph[b][a] = false;
                    indegree[a] -= 1;
                    indegree[b] += 1;
                }
            }

            // 위상 정렬
            List<Integer> result = new ArrayList<>();
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int i=1; i<n+1; i++){
                if(indegree[i] == 0){
                    queue.add(i);
                }
            }
            // 위상 정렬 결과가 오로지 하나인지? : 정확한 순위를 찾을 수 없다
            boolean certain = true;
            // 그래프 내 사이클이 발생하는지? : 데이터에 일관성이 없다.
            boolean cycle = false;

            for(int i=0; i<n; i++){
                if(queue.size() >= 2){
                    certain = false;
                    break;
                }
                if(queue.size() == 0){
                    cycle = true;
                    break;
                }
                int now = queue.poll();
                result.add(now);
                for(int j=1; j<n+1; j++){
                    if(graph[now][j]){
                        indegree[j] -= 1;
                        if(indegree[j] == 0){
                            queue.add(j);
                        }
                    }
                }
            }

            if(cycle){
                System.out.println("IMPOSSIBLE");
            }
            else if(!certain){
                System.out.println("?");
            }
            else{
                for(int i : result){
                    System.out.print(i);
                    System.out.print(" ");
                }
                System.out.println("");
            }
        }
    }
}