n명의 사람(0에서 n - 1까지 레이블이 지정됨)이 있고 그 중 한 명의 유명인이 있을 수 있다고 가정합니다. 다른 n - 1명의 사람들이 모두 x를 알고 있지만 x는 그들 중 누구도 알지 못할 때 사람 x가 유명인이라고 말할 수 있습니다. 여기서 우리는 유명인이 누구인지 찾거나 연예인이 없는지 확인해야 합니다.
우리는 'A'라는 사람에게 "안녕, A. B를 아십니까?"라는 한 가지 질문만 할 수 있습니다. A가 B를 알고 있는지 여부에 대한 정보를 얻으려면. 우리는 유명인을 찾기 위해 최소한의 질문을 해야 합니다. 그래프라는 입력으로 리스트 목록이 있는데, i번째 사람이 j번째 사람을 알면 graph[i,j] =1, 그렇지 않으면 0입니다.
따라서 입력이 그래프 =[[1,1,0],[0,1,0],[1,1,1]],
와 같은 경우
0과 2는 모두 그를 알고 있지만 1은 아무도 모르기 때문에 유명인은 1로 레이블이 지정된 사람이므로 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
know() 함수를 정의하면, b,
-
그래프[a, b]가 참일 때 참을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
하나의 스택 정의
-
initialize i :=0의 경우, i
-
i를 st에 삽입
-
-
크기가 st> 1인 동안 −
-
x :=st의 최상위 요소
-
st
에서 요소 삭제 -
y :=st의 최상위 요소
-
st
에서 요소 삭제 -
know(x, y)가 참이면 -
-
y를 st에 삽입
-
-
그렇지 않으면
-
x를 st에 삽입
-
-
-
x :=st의 최상위 요소
-
initialize i :=0의 경우, i
-
i가 x와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
know(x, i)가 참이거나 know(i, x)가 거짓이면 -
-
반환 -1
-
-
-
x를 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<vector<int<> graph;
public:
Solution(vector<vector<int<> &graph){
this->graph = graph;
}
bool knows(int a, int b){
return graph[a][b];
}
int findCelebrity(int n) {
stack<int< st;
for (int i = 0; i < n; i++) {
st.push(i);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
int y = st.top();
st.pop();
if (knows(x, y)) {
st.push(y);
}
else {
st.push(x);
}
}
int x = st.top();
for (int i = 0; i < n; i++) {
if (i == x)
continue;
if (knows(x, i) || !knows(i, x)) {
return -1;
}
}
return x;
}
};
main(){
vector<vector<int<> v = {{1,1,0},{0,1,0},{1,1,1}};
Solution ob(v);
cout << (ob.findCelebrity(3));
} 입력
{{1,1,0},{0,1,0},{1,1,1}}
3 출력
1