백준 14653번 너의 이름은 :: 마이구미

이 글은 백준 알고리즘 문제 14653번 "너의 이름은" 을 풀이한다.

2017 선린고에서 열린 천하제일 코딩대회 본선 문제에 속하면서, 가장 정답률이 낮은 문제가 된다.

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

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

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

카카오톡 채팅방을 떠올리면서 문제를 접근하면 좀 더 문제를 이해하기에 도움이 될 것이다.

문제에서 대부분 틀린 이유는 다음과 같다.

5 4 3
1 A
3 C
3 B
3 A

위와 같이 주어졌을 경우, 3번째 메시지를 읽지 않은 가능성이 있는 사람은 누굴까?

문제를 틀렸다면, 대부분 C D E 라고 생각했을 것이다.

B는 송신자이기 때문에 메시지를 읽었다.

A는 항상 읽기 때문에 읽었다.

=> 그리하여 답은 C D E

위와 같이 생각하면 안된다.

이유는 다음과 같다.

3번째 이전인 2번째 메시지에서 읽지 않은 사람이 3이다.

3번째 메시지이 읽지 않은 사람과 수가 같다.

이것이 의미하는 것은 2번째와 3번째 메시지를 읽지 않는 사람은 같다는 것이다.

즉, C라는 사람도 3번째 메시지를 읽었다는 뜻이 된다. 

카카오톡 채팅방을 떠올려라. C는 2번째 메시지를 쓰고 나가지 않고 있다가 3번째 메시지까지 읽게 된 것이다

private void solve() {
    int n = sc.nextInt();
    int k = sc.nextInt();
    int q = sc.nextInt();
    boolean[] read = new boolean[26];
    int[] array = new int[10001];
    int[] count = new int[10001];
 
    for (int i = 1; i <= k; i++) {
        count[i] = sc.nextInt();;
        array[i] = sc.next().toCharArray()[0] - 'A';
    }
 
    if (count[q] == 0) {
        System.out.println(-1);
        return;
    }
 
    for (int i = k; i >= q; i--) {
        read[array[i]] = true;
    }
 
    //이전 메시지와 읽지 않은 사람 수가 같을 경우
    for (int i = q; i > 1; i--) {
        if (count[i] != count[i - 1]) {
            break;
        }
        read[array[i]] = true;
        read[array[i - 1]] = true;
    }
 
    for (int i = 1; i < n; i++) {
        if (!read[i]) {
            System.out.print((char) (i + 'A') + " ");
        }
    }
}