백준5914 Cow Photography

작성일 | In

문제 링크

  • http://icpc.me/5914

문제 출처

  • USACO 2011 December Gold 1번
  • USACO 2011 December Silver 1번
  • 2018 IOI 여름학교 3일차 4번 문제

사용 알고리즘

  • 정렬

시간복잡도

  • O(NlgN)

풀이

사진찍겠습니다!
2018년 여름학교 3일차에 “처음반 친구들”이라는 이름으로 나온 문제입니다.

이동한 소들이 모두 다르다는 것을 통해 전-후 관계가 동일한 쌍이 과반수, 즉 3번 이상 나온 경우 그 두 소의 위치 관계를 확정할 수 있고, 그것을 이용해 정렬을 하면 된다.

쌍을 찾는 방법은 O(N2), O(NlgN), O(N)이 있다.
이 중 O(Nlg⁡N) 이하의 시간 복잡도를 갖는 방법을 사용하면 된다. 그 후, O(Nlg⁡N) 정렬을 수행하면 쉽게 풀 수 있다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

map<int, int> m[5]; //{key: 학생 번호, data: 위치}
int ans[20010] = {0};

bool cmp(int a, int b){
	int cnt = 0;
	for(int i=0; i<5; i++){
		int apos = m[i][a];
		int bpos = m[i][b];
		if(apos > bpos) cnt++;
	}
	return cnt<3;
}

int main(){
	int n; scanf("%d", &n);
	for(int i=0; i<5; i++){
		for(int j=0; j<n; j++){
			int num; scanf("%d", &num);
			if(i == 4) ans[j] = num; //조건문에서 4 대신 0~3 중 하나를 써도 무관하다.
			m[i][num] = j;
		}
	}
	sort(ans, ans+n, cmp);
	for(int i=0; i<n; i++) printf("%d ", ans[i]);
}