[14653번] 너의이름은

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

카카오톡을 자주 이용했다면 이해하기 쉬운 문제이다.

누가 읽었는지 확인하기위해 카톡에서 계산해봤던 적이 많을 것이다.

이 문제는 그 내용을 코드로 옮겨 적는 문제다.

다음과 같이 조건을 적용하면 누가 안 읽은지 추측이 가능하다.

1. A는 무조건 읽으니 true이다.

2. 이전에 메시지를 보냈던 사람일때 그 사람의 메시지 읽은수와 현재 읽은수가 같으면 그사람은 읽었다는 의미이다.

3. 현재 메시지 이후로 메시지를 보낸 모든 사람들 또한 읽었다는 뜻이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
pair<int, char> msg[10005];
 
bool chk[200];
int main()
{
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
 
    for (int i = 0; i < k; i++)
        scanf("%d %c", &msg[i].first, &msg[i].second);
 
    // A는 무조건 읽는다.
    chk['A'] = true;
 
    // 이전에 메시지를 보낸 사람의 읽은 수와 현재 q의 읽은수가 동일하면
    for (int i = 0; i < k; i++)
    {
        if (msg[i].first == msg[q - 1].first)
            chk[msg[i].second] = true;
    }
 
    // 현재 메시지 이후로 모든 보낸 사람들 true
    for (int i = q - 1; i < k; i++)
        chk[msg[i].second] = true;
 
    // 현재 메시지를 모두 읽었다면
    if (msg[q-1].first == 0)
        printf("-1");
 
    else
        for (int i = 'A'; i <= 'A' + n - 1; i++)
            if (!chk[i])
                printf("%c ", i);
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>