LeetCode에서도 유사한 문제를 풀었었다.

http://ergate.tistory.com/entry/LeetCode-169-Majority-Element


그때는 제약 조건이 훨씬 적어서 sort후, 중간값을 찾아서 이를 return해주면 되는 방법으로 아주 쉽게 해결을 했지만, 이쪽 문제는 조금 더 제약 조건이 심하다.


버퍼를 사용할 수 없도록 공간복잡도가 O(1)이다.

-> 만약 이 조건이 없었더라면 아마 map이나 vector에 저장하고, 순차적으로 돌면서 count가 절반을 넘는 것이 있는지 확인하여 return했을 것이다.

해당 숫자가 무엇인지 return하는 것이 아니라 index를 리턴해야 한다.

-> 이래서 sort할 수 없었다. (정상적이라면 c++에서 reference 변수로 들어오기 때문에 그렇게 해도 상관없긴 하지만, 아마 테스트에서는 이미 정답 index가 무엇인지 들고 있을 것이기 때문에 이렇게 하면 통과할 수 없으리라 판단했다.)


결국 Boyer-Moore vote algorithm을 활용하는 방법으로 선회했다.

(그나마 지난번 문제를 풀면서 해당 알고리즘이 있다는 것을 알았으니 다행이다,)

그런데 보이어 무어 투표 알고리즘은 만능이 아니어서 약간의 확인 과정이 필요하다.


1. [2, 1, 1, 3]

-> 단순 구현을 하면 인덱스로는 3을 리턴하게 된다.

-> 마지막에 count가 0인 상황이라면 없는 것으로 체크해야한다.


2. [2, 1, 1, 3, 4]

-> 이렇게 하면 count는 1인 상태로 4를 리턴하게 된다.

-> 결국 나온 값을 다시 루프를 돌면서 총 count를 확인해야한다.


즉, 보이어 무어의 투표 알고리즘은 확실하게 과반이 넘는다는 가정 하에서만 맞는 알고리즘인 것이다.

구현을 해보니 이 부분의 맹점을 알았다.



int solution(vector<int> &A)
{
    /*
     * Can not use sort and count
     * Limit of space complexity is O(1)
     * Return value is index of target number
    */
    int nRet = -1;
    int nIdx = 0;
    int nVal = 0;
    int nCnt = 0;
    int nTarget = 0;
    
    //! Boyer-Moore vote algoritm
    while( nIdx < A.size() )
    {
        if( nVal != A[nIdx] )
        {
            if( nCnt == 0 )
            {
                nTarget = nIdx;
                nCnt = 1;
                nVal = A[nIdx];
            }
            else
                --nCnt;
        }
        else
            ++nCnt;
        
        ++nIdx;
    }
    
    //! check target value is more than half
    if( nCnt > 0 )
    {
        nCnt = 0;
        for( int i : A )
        {
            if( i == nVal )
                ++nCnt;
        }
        if( nCnt > (A.size() / 2) )
            nRet = nTarget;
    }
    
    return nRet;
}



정확도 100%, 성능 100%

저작자 표시 비영리 변경 금지
신고

'Programming > C,C++' 카테고리의 다른 글

[Codility] MinPerimeterRectangle  (0) 2017.12.06
[Codility] MaxProfit  (0) 2017.12.06
[Codility] Dominator  (0) 2017.12.05
[Codility] StoneWall  (0) 2017.12.05
[Codility] Nesting  (0) 2017.12.05
[Codility] Brackets  (0) 2017.12.05

+ Recent posts