[LeetCode][c++] 997. Find the Town Judge

Table of Contents

• 문제
• 예제
• 상황 파악
• 계획
• 풀이
  • 1. 제출 답안
    • 리뷰
    • 코드
  • 2. 최소 런타임 샘플 답안
    • 리뷰
    • 코드

문제

원문 보기 : [LeetCode] 997. Find the Town Judge

마을에 1부터 n까지 라벨된 n명의 사람이 있다. 이중 하나가 비밀 마을 심판(town judge)이라는 루머가 있다.

만약 마을 심판이 있다면:

마을 심판은 누구도 믿지 않는다.

심판을 제외한 마을 사람 전부가 심판을 믿는다.

위 두 조건을 충족하는 사람은 정확히 한 명 있다.

trust 배열이 주어진다. trust[i] = [a_i, b_i]에서, a_i가 b_i를 믿는다는 의미이다.

마을 심판이 있다면 심판의 번호를, 없다면 -1을 반환하라.

조건(Constraints):

• 1 <= n <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• trust 배열의 모든 쌍은 유일하다.
• ai != bi
• 1 <= ai, bi <= n

예제

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

상황 파악

1. 상황 파악: 모든 사람이 그를 믿지만 그는 아무도 믿지 않는 한 사람 찾기 == 방향 그래프인데, 모든 정점으로부터 들어오는 화살표는 있지만 스스로 나가는 화살표가 없는 정점을 찾아야 한다.
2. 행렬로 표현하면 적어도 사람 눈으로는 확인하기 쉽다. 자기 자신을 제외하고 한 열이 모두 믿음을 받고, 자기 자신의 행은 아무도 믿지 않는 번호를 찾으면 된다.
3. 입력받은 배열을 행렬에 표시하고 검사하자. 자신의 행이 비어있는지 확인하고, 비어있다면 열이 모두 채워져 있는지 확인한다. 편의를 위해 자기 자신은 항상 믿는다고 표시해두는 것도 필요하다면 사용할 수 있다.
4. 검사 시간을 줄이기 위해 한 명이라도 다른 사람을 믿은 적이 있는 사람은 심판 용의자에서 제외하게 할 수 있다.
5. 언어는? cpp 파이썬 둘 다 괜찮겠지만 2차원 배열 초기화는 cpp가 편하다.

계획

1. 입력받은 주민의 수로 2차원 배열 생성 → cpp는 변수로 정적 배열을 만들 수 없으니 벡터를 쓰자. 포인터도 되긴 하는데 굳이? 싶다. 그리고 심판 용의자를 표시할 1차원 벡터도 하나 두자.
2. 반복문으로 주민의 신뢰관계를 2차원 배열에 표시하면서 용의자도 골라둔다.
3. 표시가 끝나고 남은 용의자들의 행과 열을 검사해 심판을 찾는다
4. 있으면 정답 반환, 없으면 -1

풀이

영어 지문 해석부터 정답 통과까지 총 해결 시간 34분 56초

1. 제출 답안

Runtime 213 ms, Beats 64.18%
Memory 63.7 MB, Beats 57.68%

리뷰

• 15분을 목표로 시간을 재고 해봤는데 두 배 이상 나와서 좀 놀랐다. 머리가 낡았어. 지문이 영어로 써있어서 해석하는 시간을 감안해도 길다.
• 원래 15분 이상 걸리면 빠르게 포기하고 풀이를 볼 생각이었지만 생각난 풀이가 아주 확실해서 써보고 틀리자는 마음으로 끝까지 썼다. 맞긴 맞았다.
• 통과 이후 시간을 코드에 수정할만한 부분이 있나 생각해봤는데, 풀이를 전면 수정하지 않고서는 딱히 고칠 데가 안 보일 것 같아서 샘플 답안을 보기로 했다.
• 다음엔 각 단계별 시간도 확인해볼 생각이다. 지문 해석하는 시간은 그렇다 쳐도, 계획 초안 잡는 시간이 너무 오래 걸리면 모르는 문제다. 코드 쓰는 시간이 오래 걸리는 건 진짜로 실력이 낡아서 그런 거니까 문제를 많이 푸는 수밖에 없다.

코드

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // 마을 주민의 번호가 1부터 시작하기 때문에 인덱스 주의
        vector<vector<bool>> trust_mat(n + 1, vector<bool>(n + 1, false)); // 신뢰 관계 행렬, 전부 false로 초기화
        vector<bool> judge_suspect(n + 1, true); // 마을 심판 용의자 배열, 전부 true로 초기화

        for (auto& i : trust) {
            trust_mat[i[0]][i[1]] = true; // 신뢰 관계 행렬 입력
            judge_suspect[i[0]] = false; // 한 명이라도 믿는 사람이 있다면 용의자 제외
        }

        for (int i = 1; i <= n; i++) { // 모든 마을 주민에 대해 반복
            if (!judge_suspect[i]) // 용의자가 아니라면 패스
                continue;
            for (int j = 1; j <= n; j++) { // 심판 용의자에 대해
                if (i == j)
                    continue;
                if (trust_mat[i][j] || !trust_mat[j][i]) {
                    // 한 명이라도 자신이 믿는 주민이 있거나, 자신을 믿지 않는 주민이 있다면 거짓
                    judge_suspect[i] = false;
                    break;
                }
            }
            if (judge_suspect[i]) // 검사 후에도 용의자가 true라면 정답
                return i;
        }

        return -1; // 모든 용의자가 심판이 아니었을 경우 마을에 심판 없음
    }
};

2. 최소 런타임 샘플 답안

Runtime 141 ms

리뷰

1. 풀이 설명
   1. 두 배열을 준비한다. 하나는 마을 사람이 다른 사람을 신뢰한 수, 다른 하나는 마을 사람이 다른 사람에게 신뢰받은 수이다.
   2. 주어진 신뢰 배열을 이용해 두 배열을 채운다.
   3. 마을 사람의 수만큼 위에서 채운 두 배열을 확인한다: 다른 사람을 신뢰한 수가 0이고, 신뢰받은 수가 (n - 1)이면 정답으로 반환하고, 아무것도 반환하지 않고 반복문이 끝났다면 -1을 반환한다.
2. 내가 2차원 배열로 일일이 표시하고 확인했던 것을 1차원 배열 두 개로 간단히 해결했다. 마을 사람들의 신뢰 관계를 보존할 필요가 없었다. 주어진 데이터를 너무 보존하려고 신경쓰지 말자! 맨날 그대로 옮겨 적으려고 하니까 과정이 많아지고 런타임이 길어지는 거다.
3. 중요해 보이니까 강조하자. 주어진 데이터는 원하는 답을 찾을 수 있는 선에서, 얼마든지 변형해도 된다. 널부러진 값으로부터 유용한 정보를 만들어내는 게 내가 할 일인데 항상 옮겨적기만 하니까 시야가 계속 좁은 거다.

코드

주석은 내가 추가했다.

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> a(n, 0); // 타인을 신뢰한 수
        vector<int> b(n, 0); // 타인에게 신뢰받은 수
        for (auto& t : trust) {
            ++a[t[0] - 1];
            ++b[t[1] - 1];
        }
        for (int i = 0; i < n; ++i) {
            if ((a[i] == 0) && (b[i] == (n - 1))) return (i + 1);
        }
        return -1;
    }
};