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)가 존재해야 한다.

그런데 둘 다 존재하지 않기 때문에 학생들이 잘못된 명단을 제시한 것이다.

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

줄서기 timer 1초 memory 128MB

줄서기 1초 128MB