[BOJ 14864] 줄서기

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

14864번: 줄서기

 

- 문제 요약

 

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

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

 

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

 

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

 

 

- 알고리즘 정리

 

ll w=i+p[i].first-p[i].second

=> i번째 카드에 적힌 숫자보다 작은 수가 적혀있는 카드의 개수입니다.

 

check[w]

=> 문제에서 "각 학생은 1부터 N까지 서로 다른 번호가 적힌 카드들 중 하나를 가지고 있다"라고 했으니, 값이 중복되는 경우는 카드 번호를 알 수 없는 경우로 간주합니다. 그러므로 이런 경우에는 -1을 출력하고 프로그램을 종료시킵니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
typedef long long ll;
ll n,m,result[MAX];
bool check[MAX];
pair<int,int>p[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		p[a].first++;
		p[b].second++;
	}
	for(int i=1;i<=n;i++){
		ll w=i+p[i].first-p[i].second;
		if(check[w]){
			cout<<-1;
			return 0;
		} 
		result[i]=w;
		check[w]=true;
	}
	for(int i=1;i<=n;i++){
		cout<<result[i]<<" ";
	}
}

코드 제출 결과

처음에 문제 보고 https://www.acmicpc.net/problem/2252 이랑 비슷한 형태라서 위상정렬 문제라고 착각했네요 ㅋㅋ;;