[LeetCode] 277. Find the Celebrity

 파티에 초대된 사람들의 정보가 리스트로 주어지고, 각 리스트의 요소는 그 사람이 다른 사람을 알고 있으면 1, 모르면 0으로 주어진다. 유명인사(Celebrity)는 다른 사람은 모두 모르지만 모든 사람이 그 사람을 알고있고, 그 사람은 오직 1명이거나 없다. 없으면 -1 있다면 그 사람의 인덱스를 반환하면 된다.

 Constraint의 n의 최대값이 100 밖에 되지 않아 3개의 반복문을 중첩(O(n))해 풀어 모든 테스트 케이스를 만족했지만, 효율적이진 않다. 효율적인 풀이는 O(n)으로도 가능한데 주어진 리스트의 0번부터 Celebrity 용의자를 추척하고(knows(celebrity, i)가 False 일 때까지), 용의자가 누군가 한 명이라도 알아 True을 반환하면 -1을 그렇지 않다면 해당 용의자의 index를 반환할 수 있다.

 

class Solution:
    def findCelebrity(self, n: int) -> int:
        for i in range(n):
            flag = 0
            for j in range(n):
                if knows(j, i) == 0:
                    flag = 1
                    break
            if flag == 0:
                for j in range(n):
                    if i == j:
                        continue
                    if knows(i, j) == 1:
                        flag = 2
                        break
            if flag == 0:
                return i

        return -1