이건 문제 이해가 조금 어려울 수 있다.


For example, given array H containing N = 9 integers:


H[0] = 8 H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7 H[7] = 4 H[8] = 8

the function should return 7. The figure shows one possible arrangement of seven blocks.




생각을 해보니(어차피 해당 파트가 stack과 queue이긴 하지만...)

1. 맨 처음 값을 넣고 다음부터 비교하기 시작한다

2.1. 작은 값이 나온 경우

-> 현재 값을 빼고 다시 체크한다

-> 만약 다시 체크할게 없을 경우, 해당 값을 스택에 넣고 다시 돌기 시작한다

2.2. 큰 값이 나온 경우

-> 해당 값을 스택에 넣고 돌기 시작한다



#include <stack>

int solution(vector<int> &H)
{
    int nRet = 0;
    
    stack<int> kStack;
    if( H.size() > 0 )
    {
        kStack.push(H[0]);
        ++nRet;
        
        int i = 1;
        while( i < H.size() )
        {
            if( H[i] > kStack.top() )
            {
                kStack.push(H[i]);
                ++nRet;
            }
            else if( H[i] < kStack.top() )
            {
                kStack.pop();
                if(kStack.size() > 0)
                    continue;
                kStack.push(H[i]);
                ++nRet;
            }
            
            ++i;
        }
    }
    
    return nRet;
}



정확도 100%, 성능 100%

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

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

[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
[Codility] MaxProductOfThree  (0) 2017.12.05

+ Recent posts