[백준] 14653 - 너의 이름은

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

14653번: 너의 이름은

알고리즘 분류는 문자열, 구현으로 되어있다.

구현 문제가 맞기는 한데, 개인적으로 실버5 난이도보다는 살짝 높은 난이도의 구현이라고 생각했다.

---

풀이 아이디어

---

이 문제는 메세지를 보낸 사람과 그 메세지를 읽지 않은 사람의 숫자가 주어질 때,

임의로 선택한 메세지를 읽지 않은 가능성이 있는 사람을 모두 찾는 문제이다.

 

처음 이 문제를 봤을 때는 풀이 방법이 잘 감이 오지 않았지만,

입력으로 주어지는 메세지의 숫자에서 힌트를 얻었다.

 

제한시간이 2초인데, 입력으로 들어오는 메세지의 숫자가 10000이다.

그렇다면 O(n^2) 의 시간복잡도로도 충분히 풀 수 있다는 뜻이다.

그리고 이 문제의 핵심은 바로 이 문장이다.

 

"만약 어떤 시점에 메시지를 읽거나 보냈다면, 그 시점 이전에 수신된 메시지는 모두 읽은 것으로 처리된다."

 

처음에는 문제에서 주어진 '읽지 않은 사람의 숫자'가 현재 메세지를 보낸 시점에서 읽지 않은 사람의 숫자인지,

아니면 전체 총 메세지에 대해서 읽지 않은 사람의 숫자인지 헷갈렸었다.

이 문제는 후자를 의도하고 낸 문제이다.

 

그렇다면 풀이 방법은 매우 간단해지는데, 아래의 알고리즘을 사용하면 된다.

 

1. 어떤 사람이 메세지를 읽을 때마다, 그 앞의 메세지를 읽은 사람에 그 사람을 추가해주면 된다.

 

나는 이걸 구현하기 위해 집합(set)을 사용했다.

2 A

2 B

2 A

2 B

와 같은 입력이 주어진다면, B를 중복해서 넣을 우려가 있기 때문이다.

(문제에서 A는 항상 읽는다고 했기 때문에, A는 고려하지 않았다.)

 

그런데 이렇게만 풀면 문제를 틀리게 된다.

다음과 같은 반례가 있기 때문이다.

 

5 4 3

2 A

2 B

2 A

3 C

 

상기한 첫번째 파트만 알고리즘에 적용하면,

3번째 메세지를 읽지 않은 사람 후보로 B D E 를 출력하지만, 실제 답은 D, E 이다.

2번째에서 B가 읽었다는 것을 확인한 상태에서,

3번째에 읽지 않은 사람의 숫자가 변하지 않았다는 말은, B는 계속해서 읽고 있었다는 뜻이다.

 

이게 성립되는 이유는 '메세지를 읽지 않은 사람의 숫자'가

"전체 총 메세지에 대해서 읽지 않은 사람의 숫자" 이기 때문이다.

 

2번째까지 B가 읽고, 3번째에서 B가 읽지 않았다고 가정해보면,

읽지 않은 사람의 숫자는 반드시 증가했어야 한다.

 

만약 B가 3번째에 읽지 않았다가 한참 나중에 읽었다고 한다면,

나중에 메세지를 읽는 순간, 3번째 메세지도 B가 읽은 것으로 처리되기 때문에,

"전체 총 메세지에 대해 읽지 않은 사람의 숫자"에 B가 읽은 것이 반영되어있어야 한다.

따라서 다음 알고리즘이 추가되어야 한다.

 

2. 만약 읽지 않은 사람의 숫자가 이전 메세지와 같다면,

이전 메세지의 '읽지 않은 사람 목록'과 현재 메세지의 '읽지 않은 사람의 목록'은 같다.

 

이 두가지를 고려하여 알고리즘을 작성하면 문제를 풀 수 있다.

---

소스 코드

---

import sys, copy
input = sys.stdin.readline
people, message, checkingMessage = map(int, input().split())
whoRead = [{'A'} for _ in range(message)]
notReadCount = []
for i in range(message):
    notRead, sender = input().split()
    notReadCount.append(int(notRead))

    # 보낸 사람이 A가 아니면 내가 메세지를 보내기 위해서 앞의 모든 메세지를 읽었어야 하므로 앞에 읽은 모든 메세지에 나를 추가
    if sender != 'A':
        for j in range(0, i):
            whoRead[j].add(sender)

    # 읽지 않은 사람의 숫자가 그대로라면, 직전 상태와 현재 상태가 같다는 의미이다.
    if i > 0 and notReadCount[i] == notReadCount[i-1]:
        whoRead[i] = copy.deepcopy(whoRead[i-1])

    # 현재 메세지를 읽은 사람에 나를 추가
    whoRead[i].add(sender)


if notReadCount[checkingMessage-1] == 0:
    print(-1)
else:
    for i in range(people):
        if chr(ord('A') + i) not in whoRead[checkingMessage-1]:
            print(chr(ord('A') + i), end=' ')