Lesson 8. Leader - Dominator #3-1

Dominator #1에서는 map을 이용해서 풀었다.

Dominator #2에서는 정렬을 이용해서 풀었다.

이번에는 stack을 이용해서 풀어본다.

 

1. 아이디어

대표값이 가장 많이 등장하는 값이므로, 서로 다른 값들을 지우면, 결국 대표값만 남게 될 것이다.

stack을 이용하면, 서로 다른 값들을 간단하게 지울 수 있다.

 

예시)

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]
3	4	3	2	3	-1	3	3

 

stack으로 담으면 다음과 같이 된다.

stack에는 대표값 최종적으로 남게 된다.

	4		2		-1		3
3	3	3	3	3	3	3	3
push	remove	push	remove	push	remove	push	push

 

 

2. 문제풀이 전략

1. stack이 비어 있으면, 값을 넣는다
2. stack에 값이 있으면, 현재 값과 같은지 비교한다
3. 같으면 현재 값을 stack에 push
4. 다르면 stack 값 삭제
5. stack에 최종 남아 있는 값을 대표값으로 설정
6. 대표값이 배열에 몇 번 등장하는지 확인 (배열 전체탐색)

 

 

3. 코드 (C++)

#include <stack>

int solution(vector<int> &A) {
    
    if(A.empty()) return -1;

    //stack을 이용한 서로 다른 값 삭제
    stack<int> candidate = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        if(candidate.empty())
        {
            candidate.push(A[i]);
        }
        else
        {
            if(A[i] != candidate.top()) 
            {
                candidate.pop();
            }
            else
            {
                candidate.push(A[i]);
            }
        }
    }

    int dominator = candidate.top();  //대표값
    
    //대표값 등장 횟수 세기(전체탐색)
    int cnt = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == dominator) cnt++;
    }
    
    //대표값이 등장 횟수 조건을 충족하는지 확인
    if(cnt <= A.size() / 2) return -1;

    auto it = find(A.begin(), A.end(), dominator);
    int idx = distance(A.begin(), it);

    return idx;
}

 

 

4. 결과