[Python/BOJ] 14653. 너의 이름은

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

14653번: 너의 이름은

문제

OAKAK TALK에는 신기한 기능이 있다. 바로 메시지 옆에 아직 안 읽은 사람의 수를 표시해주는 기능이다. 하지만 이 기능은 읽지 않은 사람의 수만 표시해줄 뿐, 메시지를 읽지 않은 사람이 누구인지는 표시해주지 않는다. 따라서 이 기능으로 메시지를 몇 명이 읽었는지는 알 수 있지만, 누가 읽었는지는 알 수 없다. 하지만 특정한 조건을 만족한다면, 우리는 메시지를 읽지 않은 사람을 유추해낼 수 있다.

그 조건은 다음과 같다. N명이 있는 OAKAK TALK방이 있다. 그리고 그 방에는 K개의 메시지가 있다. 각각의 메시지는 해당 메시지의 송신자와 읽지 않은 사람의 수에 대한 정보를 담고 있다. 만약 어떤 시점에 메시지를 읽거나 보냈다면, 그 시점 이전에 수신된 메시지는 모두 읽은 것으로 처리된다.

Q번째 메시지를 읽지 않은 사람을 유추 가능한대로 모두 구해보자! 사람의 이름은 편의상 A, B, C, …, Z라고 하며, N명의 이름은 A부터 사전 순서대로 N개의 알파벳이 부여된다. “나”의 이름은 A이고 “나”는 항상 모든 메시지를 읽는다.

입력

첫째 줄에 OAKAK TALK방에 있는 사람 수 N과 총 메시지의 개수 K, 정보를 알고 싶은 메시지의 번호 Q가 주어진다. (1 ≤ N ≤ 26, 1 ≤ K ≤ 10,000, 1 ≤ Q ≤ K) 둘째 줄부터 K개의 줄에 걸쳐 메시지를 읽지 않은 사람의 수 R과 그 메시지 송신자의 이름 P가 하나의 공백을 사이에 두고 주어진다. 메시지를 읽지 않은 사람의 수는 항상 이전 메시지를 읽지 않은 사람의 수보다 크거나 같고, 모순되는 입력은 없음이 보장된다.

출력

메시지를 읽지 않았을 가능성이 있는 모든 사람의 이름을 사전 순서대로 하나의 공백을 사이에 두고 출력한다. 모든 사람이 메시지를 읽어 출력할 이름이 없는 경우에는 –1을 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n, _, q, messages) :
    # 1. 알고 싶은 메시지의 안 읽은 사람 수 구하기
    stand = messages[q][0]
    # 2. 모두 읽은 경우
    if stand == '0' : print(-1)
    # 3. 안 읽은 사람이 있는 경우
    else :
        # 3-1. A를 제외한 전체 인원을 set 자료형 변수에 설정
        mod = {chr(i) for i in range(66, 65 + n)}
        # 3-2.
        for not_read, who in messages[1:] :
            # 읽지 않은 사람이 기준 수 이상인 경우
            if int(not_read) >= int(stand) :
                # 메시지를 보낸 사람은 제외
                mod.discard(who)
        # 3-3. 결과 출력
        print(*sorted(mod))

if __name__ == '__main__' :
    n, k, q = map(int, input().split())
    messages = [0] + [list(map(str, input().rstrip().split())) for _ in range(k)]
    solution(n, k, q, messages)