백준14653 너의 이름은

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14653

문제 출처

  • 제1회 천하제일 코딩대회 본선 D번

시간복잡도

  • O(n+k)

풀이

메시지를 읽은게 확실한 사람은

  1. q번째 메시지를 보낸 사람
  2. q번째 메시지를 보낼 때와 읽은 사람 수가 같은 메시지의 전송자
  3. q번째 메시지 이후 메시지 전송자

이걸 간단히 하면
(q번째 메시지를 읽은 사람 수) <= (마지막 메시지를 읽은 사람의 수)
를 만족하는 모든 메시지의 전송자입니다.

전체 코드

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

int n, k, q;
int num[10001], who[10001];
int chk[26];

int main(){
	cin >> n >> k >> q;
	for(int i=1; i<=k; i++){
		int a;
		char b;
		cin >> a >> b;
		num[i] = a; who[i] = b;
	}

	if(num[q]==0){
		printf("-1");
		return 0;
	}

	for(int i=1; i<=k; i++){
		if(num[q] <= num[i]) chk[who[i]-'A']=1;
	}

	chk[0] = 1;

	for(int i=0; i<n; i++){
		if(!chk[i]) printf("%c ", i+'A');
	}
}