The Celebrity Problem
파티에 n명의 사람이 있고, 각 사람은 0부터 n-1까지 번호가 매겨져 있습니다. matrix[i][j]가 사람 i가 사람 j를 알고 있으면 1, 그렇지 않으면 0인 n × n 행렬이 주어집니다. 아는 관계는 일방적일 수 있습니다. 즉, i는 j를 알지만 j는 i를 모를 수 있습니다.
유명인은 다른 모든 사람이 알고 있지만 아무도 알지 못하는 사람입니다. 유명인의 번호를 반환하고, 유명인이 없으면 -1을 반환하세요.
함수
- matrixinteger-2d-array
- 누가 누구를 아는지: i행 j열은 사람 i가 사람 j를 알고 있으면 1이다
- 반환값integer
- 유명인의 번호, 없으면 -1
제약 조건
2 ≤ n ≤ 150, 여기서n은 행과 열의 개수입니다matrix[i][j]는0또는1입니다.matrix[i][i] = 0모든 사람에 대해
예제
- 입력
- matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
- 출력
- 1
- 설명
- 1행은 모두 0이므로, 1번 사람은 아무도 모릅니다. 1열의 0행과 2행에는 1이 있으므로, 다른 두 사람 모두 1번 사람을 알고 있습니다. 1번 사람이 유명인입니다.
- 입력
- matrix = [[0, 1], [1, 0]]
- 출력
- -1
- 설명
- 사람 0은 사람 1을 알고 사람 1은 사람 0을 압니다. 둘 다 누군가를 알고 있으므로 어느 쪽도 유명인일 수 없으며, 답은 -1입니다.
- 입력
- matrix = [[0, 0, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1], [0, 1, 1, 0]]
- 출력
- -1
- 설명
- 다른 모든 사람은 2번 사람을 알고 있지만, 2번 행의 3번 열에는 1이 있습니다. 즉, 2번 사람은 3번 사람을 알고 있습니다. 따라서 2번 사람은 제외되며, 모든 사람에게 알려진 다른 사람도 없으므로 답은 -1입니다.
후속 질문
각 조회를 반드시 해야 하는 질문이라고 가정해 보세요. 최악의 경우 질문을 몇 개나 해야 하며, 3(n-1)보다 적게 할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
정의에 따라 모든 사람을 확인하면 행렬 전체를 읽을 수 있습니다. 두 사람
a와b를 골라 셀 하나인matrix[a][b]를 살펴보세요. 그 값이 무엇이든 두 사람 중 한 명은 유명인일 수 없습니다. 각 경우에 누구일까요?a가b를 알고 있다면,a는 누군가를 알고 있으므로 제외됩니다.a가b를 모른다면, 모든 사람이b를 아는 것은 아니므로b가 제외됩니다. 한 번 조회할 때마다 한 사람이 제거되므로,n-1번 조회하면 후보 한 명이 남습니다.양쪽 끝에 포인터를 하나씩 둡니다.
a = 0과b = n-1입니다.a < b인 동안a가b를 알고 있으면a를 앞으로 이동하고, 그렇지 않으면b를 뒤로 이동합니다. 남은 사람은 후보일 뿐입니다. 반환하기 전에 그 사람의 행과 열을 확인하세요.
풀이
모든 사람을 정의에 따라 검사하면 조회 작업이 약 2n²회 필요합니다. 하나의 셀 matrix[a][b]은 항상 a와 b 중 하나를 후보에서 제외하므로, n-1회의 조회를 하면 후보가 하나만 남습니다. 그런 다음 후보의 행과 열을 한 번씩 확인하면 그 후보가 유명인인지 판단할 수 있습니다.
모든 사람 확인
핵심 아이디어
행 c에 1이 없고(아무도 모른다), 자신의 행을 제외한 모든 행에서 열 c에 1이 있으면(모두가 그 사람을 안다) 사람 c는 유명인입니다. 각 사람에 대해 차례로 이 정의를 확인하고, 조건을 만족하는 첫 번째 사람을 반환하세요.
사람 한 명당 조회는 최대 2(n-1)회이며, 전체적으로 약 2n²회입니다. n = 150이면 조회는 약 45,000회입니다.
알고리즘
- 0부터
n-1까지 각 사람c에 대해, 다른 모든 사람other를 살펴봅니다. matrix[c][other]가 1이거나matrix[other][c]가 0이면c는 유명인이 아닙니다. 다음 사람으로 넘어갑니다.- 다른 사람이
c가 유명인이 아니라고 판별하지 못하면c를 반환합니다. - 모든 사람이 조건을 만족하지 못하면 -1을 반환합니다.
def findCelebrity(matrix):
n = len(matrix)
for c in range(n):
is_celebrity = True
for other in range(n):
# c must know no one, and everyone else must know c.
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
is_celebrity = False
break
if is_celebrity:
return c
return -1스택으로 제거하기
핵심 아이디어
matrix[a][b]가 1이면 a는 누군가를 알고 있으므로 유명인이 될 수 없습니다. 0이면 a는 b를 모르므로 b는 유명인이 될 수 없습니다. 어느 쪽이든 조회 한 번으로 한 사람을 완전히 제외할 수 있습니다. 모두를 스택에 넣고, 두 명을 꺼내 질문한 다음, 여전히 가능성이 있는 사람을 다시 넣습니다. n-1번 반복하면 한 사람만 남습니다.
그 사람은 후보일 뿐, 정답은 아닙니다. 제거 과정으로 다른 누구도 유명인이 될 수 없다는 점은 알 수 있지만, 살아남은 사람의 행과 열은 확인하지 않습니다. 세 번째 예시에서 살아남은 사람은 2번인데, 3번을 알고 있으므로 검사 결과는 -1입니다. 검사에는 조회가 2(n-1)번 더 필요하며, 전체 시간 복잡도는 O(n)입니다.
알고리즘
- 모든 사람을 스택에 넣습니다.
- 스택에 한 명보다 많은 사람이 있는 동안
a와b를 꺼냅니다. a가b를 알고 있다면b를 다시 넣고, 그렇지 않으면a를 다시 넣습니다.- 마지막 사람을 후보로 정합니다. 그 사람이 누군가를 알고 있거나, 누군가가 그 사람을 모르면 -1을 반환합니다.
- 그렇지 않으면 후보를 반환합니다.
def findCelebrity(matrix):
n = len(matrix)
candidates = list(range(n))
# Each question removes one person who cannot be the celebrity.
while len(candidates) > 1:
a = candidates.pop()
b = candidates.pop()
candidates.append(b if matrix[a][b] == 1 else a)
c = candidates[0]
# The survivor is only a candidate: check every other person.
for other in range(n):
if other != c and (matrix[c][other] == 1 or matrix[other][c] == 0):
return -1
return c두 포인터, 그런 다음 검증
핵심 아이디어
스택에는 아직 제외되지 않은 사람들만 들어 있으며, 순서는 중요하지 않습니다. 이를 두 개의 포인터로 바꾸세요. a는 첫 번째 사람을, b는 마지막 사람을 가리킵니다. a에서 b까지의 범위 밖에 있는 사람은 모두 이미 제외된 상태입니다. a가 b를 알고 있으면 a를 제외하고, 그렇지 않으면 b를 제외합니다. 포인터가 만나면 포인터가 가리키는 사람이 후보입니다.
첫 번째 예시에서 matrix[0][2]는 0이므로 사람 2가 제외됩니다. 그런 다음 matrix[0][1]은 1이므로 사람 0이 제외됩니다. 포인터는 검사에 통과하는 사람 1에서 만납니다. 조회 횟수는 n-1회에 최대 2(n-1)회가 더해지며, 추가 메모리는 정수 두 개만 사용합니다.
알고리즘
a = 0으로 설정하고b = n-1로 설정합니다.a < b인 동안:matrix[a][b]가 1이면a에 1을 더하고, 그렇지 않으면b에서 1을 뺍니다.- 후보는
a입니다. 다른 모든 사람에 대해 후보가 그들을 알지 못하고 그들은 후보를 아는지 확인합니다. - 모든 확인을 통과하면 후보를 반환하고, 그렇지 않으면 -1을 반환합니다.
def findCelebrity(matrix):
n = len(matrix)
a, b = 0, n - 1
# Each question rules out one of the two people.
while a < b:
if matrix[a][b] == 1:
a += 1 # a knows someone, so a is not the celebrity
else:
b -= 1 # a does not know b, so b is not the celebrity
# a is the only person left who could be the celebrity: check it.
for other in range(n):
if other != a and (matrix[a][other] == 1 or matrix[other][a] == 0):
return -1
return a
함정과 경계 사례
- 생존자인지 확인하지 않고 반환하기.
[[0, 1], [1, 0]]에서는 서로 아는 두 사람 중 한 명이 생존자이며, 정답은 -1입니다. - 한쪽만 확인하기. 세 번째 예제는 행에서만 실패합니다. 모두가 사람 2를 알고 있지만, 사람 2는 사람 3을 알고 있습니다.
- 대각선 요소를 세기.
matrix[c][c]는 0이므로other == c를 건너뛰지 않는 열 검사는 실제 유명인을 모두 제외합니다. - 셀을 반대로 읽기.
matrix[a][b] = 1은b가 아니라a를 제외합니다. 역할을 바꾸면 실제 유명인을 놓치게 됩니다. - Lua 또는 R에서 1부터 시작하는 인덱스를 반환하기. 사람은 0부터 번호가 매겨지므로 반환하기 전에 1을 빼세요.
자주 묻는 질문3
유명인 문제의 시간 복잡도는 얼마인가요?
제거 방식의 해법은 O(n) 시간에 실행됩니다. 후보를 찾는 조회는 n-1회이며, 후보를 확인하는 횟수는 최대 2(n-1)회입니다. 투 포인터 버전은 추가 공간 O(1)을 사용하고, 스택 버전은 O(n)을 사용합니다. 정의에 따라 모든 사람을 확인하면 O(n²)의 비용이 듭니다.
유명인이 한 명보다 많을 수 있나요?
아니요. 두 사람이 모두 유명인이라면, 각자는 모든 사람에게 알려져 있으므로 서로를 알 것입니다. 하지만 유명인은 아무도 모르므로, 파티에는 유명인이 최대 한 명만 있을 수 있습니다.
유명인 문제는 그래프와 어떤 관련이 있나요?
이 행렬은 방향 그래프의 인접 행렬입니다. i에서 j로 향하는 간선은 i가 j를 안다는 뜻입니다. 유명인은 진출 차수가 0이고 진입 차수가 n-1인 노드, 즉 보편적인 싱크입니다. 차수를 세려면 행렬 전체를 읽어야 하지만, 제거 방식은 O(n)개의 셀만 읽고 싱크를 찾습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def findCelebrity(matrix):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
matrix = [[0, 1, 0], [0, 0, 0], [1, 1, 0]]
예상 출력
1