[백준]#14864 줄서기

문제

N 명의 학생들이 앞뒤로 일렬로 서 있다. 각 학생은 1부터 N까지 서로 다른 번호가 적힌 카드들 중 하나를 가지고 있다. 학생들에게서 자신보다 뒤에 서있으면서 더 작은 번호의 카드를 가진 학생들의 명단을 하나도 빠짐없이 모두 받았다. 이 명단을 통해 학생들이 가지고 있는 카드의 번호를 알아내려고 한다.

예를 들어, 일렬로 서 있는 5명의 학생들을 앞에서부터 순서대로 “학생1, 학생2, 학생3, 학생4, 학생5”라고 하고, 학생들에게 받은 명단을 통해 다음과 같이 5개의 순서쌍이 만들어졌다고 하자. 순서쌍 (X,Y)는 학생Y 가 학생X 보다 뒤에 있으면서 더 작은 번호를 가지고 있다는 것을 의미한다.

(1,2), (1,5), (3,4), (3,5), (4,5)

이 자료를 분석하면 학생1, 학생2, 학생3, 학생4, 학생5는 각각 3, 1, 5, 4, 2가 적힌 카드를 가지고 있음을 알 수 있다.

다른 예로 5명 학생들에게 받은 명단으로 다음과 같은 6개의 순서쌍이 만들어 졌다고 하자.

(1,2), (1,3), (1,5), (2,5), (3,4), (3,5)

이 경우, 학생들이 잘못된 명단을 제시한 것이다. 순서쌍 (2,5)에 의하면 학생2는 학생5보다 큰 번호의 카드를 가지고 있다. 그런데 만일 학생4의 카드가 학생5의 카드보다 작은 번호라면 순서쌍 (2,4)가 존재해야 하고, 반대로 학생4의 카드가 학생5의 카드보다 큰 번호라면 순서쌍 (4,5)가 존재해야 한다. 그런데 둘 다 존재하지 않기 때문에 학생들이 잘못된 명단을 제시한 것이다.

학생들로부터 받은 명단으로 만들어진 순서쌍을 입력으로 받아, 학생들이 가지고 있는 카드 번호를 알아내는 프로그램을 작성하라.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학생 수 N (1 ≤ N ≤ 100,000)과 순서쌍의 수 M (0 ≤ M ≤ 1,000,000)이 공백으로 분리되어 주어진다. 일렬로 서 있는 학생들을 순서대로 학생1, 학생2, ... , 학생N 이라고 하자. 다음 M개의 각 줄에는 두 개의 자연수 X와 Y가 공백으로 분리되어 주어진다. 이것은 학생Y가 학생X 보다 더 작은 번호가 적힌 카드를 가지고 있다는 것을 의미하는 순서쌍이다 (1 ≤ X < Y ≤ N). 입력에 중복된 순서쌍은 없다.

출력

표준 출력으로, 주어진 순서쌍을 통해 학생들이 가지고 있는 카드 번호를 알 수 있으면 학생들이 서 있는 순서대로 카드번호를 공백으로 분리하여 출력한다. 그렇지 않으면 -1을 출력한다.

예제 입력 1

5 5
1 2
1 5
3 4
3 5
4 5

예제 출력 1

3 1 5 4 2

예제 입력 2

5 6
1 2
1 3
1 5
2 5
3 4
3 5

예제 출력 2

-1

풀이

이 문제는 특별한 알고리즘을 사용하지 않고 구할 수 있었다. 처음에 순서대로 서있다고 가정한 뒤에 주어진 입력에 따라 작은건 마이너스 큰건 플러스를 해주면서 계산을 해주면 답을 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int[] arr = new int[N+1];
        for(int i=1; i<=N; i++)
            arr[i] = i;

        for(int i=0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int front = Integer.parseInt(input[0]);
            int back = Integer.parseInt(input[1]);

            arr[front]++;       //뒤의 수보다 커야하기 때문에 ++
            arr[back]--;        //앞의 수보다 작아야하기 때문에 --;
        }

        if(!check(N, arr))
            System.out.println(-1);

        else {
            StringBuilder sb = new StringBuilder();

            for(int i=1; i<=N; i++) {
                sb.append(arr[i]).append(" ");
            }

            System.out.print(sb);
        }
    }
    
    public static boolean check(int N, int[] arr) {   //조건에 부합하는 지 체크
        HashSet<Integer> set = new HashSet<>();
        
        for(int i=1; i<=N; i++) {
            int temp = arr[i];
            
            if(temp>N || temp<=0) return false;   //주어진 입력이 잘못되어 1~N 범위를 벗어날 때

            if(!set.add(temp)) return false;      //주어진 입력이 잘못되어 중복인 수가 존재할 
        }
        
        return true;
    }
}