백준14864 줄서기

작성일 | In

문제 링크

  • http://icpc.me/14864

문제 출처

  • 전국 본선 초등부4, 중등부3

시간복잡도

  • O(N + M)

풀이

M = 0인 상황을 가정해봅시다. 그런 경우에는 뒤에 있는 사람이 무조건 더 큰 수를 갖고 있습니다.
1 2 3 4 … N 과 같이 카드가 배정이 되어 있습니다.

이제 순서쌍을 하나씩 입력 받으면서 처리해줍시다.
(X, Y)를 입력받으면 X가 갖고 있는 카드의 숫자를 1 증가시키고, Y의 카드는 1 감소시키면 됩니다.

M개의 순서쌍에 대한 처리가 모두 끝났다면 결과값이 정당한지 검증한 후, 적절하게 출력하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

vector<int> v;
int n, m;

void chk(){
	vector<int> visit(n+1);
	for(int i=1; i<=n; i++){
		if(v[i] > n || v[i] <= 0){
			cout << -1; exit(0);
		}
		if(visit[v[i]]){
			cout << -1; exit(0);
		}
		visit[v[i]] = 1;
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	v.resize(n+1);
	for(int i=1; i<=n; i++) v[i] = i;

	while(m--){
		int a, b; cin >> a >> b;
		v[a]++; v[b]--;
	}

	chk();
	for(int i=1; i<=n; i++) cout << v[i] << " ";
}