Lesson 8. Leader - Dominator #3-2 (코드 개선)

1. 아이디어

stack을 생성해서 모든 값을 가지고 있을 필요가 없다.

왜냐하면, stack에는 최종적으로 대표값만 있기 때문이다. 즉, 중복된 값만 stack에 남게된다.

 

 

2. 코드 (C++)

int solution(vector<int> &A) {

    if(A.empty()) return -1;

    //대표값 찾기
    int dominator = 0;
    int cnt = 0;
    for(size_t i = 0; i < A.size(); i++)
    {
        if(cnt == 0) //대표값 설정
        {
            dominator = A[i];
            cnt = 1;
        }
        else
        {
            if(A[i] != dominator) cnt--; //서로 다른 값이면, 제거
            else cnt++;
        }
    }

    //대표값 등장 횟수 세기
    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;
}

 

 

3. 결과