[백준] 14653 너의 이름은 (실버 2)

실버 2지만 반례를 찾아내기 개인적으로 굉장히 어려웠다.

 

 

큰 구성은 아래와 같다.

-> 메세지를 읽지 않은 사람들을 담은 집합을 만든다. (초기화는 A를 제외한 모든 사람으로 해준다.)

-> 톡 내용을 아래서 위로 훑으며

-> 송신자는 확실히 읽은 사람이기 때문에 집합에서 제거해준다.

-> 읽은 사람 수가 0명이라면 모든 사람이 읽은 것으로 생각한다.

 

 

이렇게 하면 간단히 문제가 풀릴 것이라고 생각했지만, 나로써는 생각하기 어려운 반례 상황이 존재했다.

 

< 입력 1 >

4 2 2

2 B

3 A

 

< 입력 2>

4 2 2

2 B

2 A

 

 

여기서 두 입력의 차이를 고려해주어야 "맞았습니다"를 받을 수 있다.

 

< 입력 1 설명 >

현재 초기화된 사람들 집합은 { B, C, D }이다. 

 

톡 내용을 아래부터 훑으며 올라오기 때문에 가장 처음 마주하는 상황은 (3, A) 이다.

 

A는 이미 제거가 되었기 때문에 따로 제거과정을 거치지는 않는다.

 

이로써 결과는 B C D를 해주면 된다.

 

< 입력 2 설명 >

현재 초기화된 사람들 집합은 { B, C, D }이다. 

 

톡 내용을 아래부터 훑으며 올라오기 때문에 가장 처음 마주하는 상황은 (2, A)이다.

 

A는 이미 제거가 되었기 때문에 따로 제거과정을 거치지는 않는다.

 

그 다음 톡내용을 확인해보니 (2 B)이다. 

 

이를 통해서 캐치해야 하는 것은 두번째 톡 또한 B가 읽었다는 사실이다.

 

결과적으로 (2, A) 상황에서의 후보는 B C D 중 2명이지만, 

 

C 나 D가 읽었다면 첫번째 톡의 읽지 않은 사람의 정보가 바뀌었을 것이다.

 

따라서 B가 읽었을 수 밖에 없고 

 

이로써 결과는 C D가 된다.

 

 

 

 

정답 코드는 아래와 같다.

 

## 9 57

import sys
input = sys.stdin.readline

N, K, Q = map(int, input().rstrip().split())
commands = []
for _ in range(K):
    commands.append(list(input().rstrip().split()))


people = set()
for asciiNum in range(66, 66+N-1):
    people.add(chr(asciiNum))

flag = 0

for index, (r,p) in enumerate(commands[::-1]):
    ##print(f"{K - index} : {r}, {p}")
    r = int(r)

    if flag > r:
        break

    ## 송신자는 당연히 톡을 읽었으므로
    if p in people:
        people.remove(p)

    ## 0이 떠있다면 모두가 읽었다는 의미이다.
    if r == 0:
        people = set()
        break


    if K - index == Q:
        flag = r



if len(people) == 0:
    print(-1)

else:
    print(*sorted(list(people)))