왜 히스토그램 문제는 O(N)인가?

너무 뻔한 이야기 일 수도 있지만, 올해 들어서 이해했기에 글로 남겨봅니다.

 

PS를 꾸준히 풀다가 보면, 히스토그램이라는 문제를 한 번쯤은 들어봤을 수 있습니다. 플레 5 기준으로 사실상 제일 많이 풀린 문제이기도 하고 종만북, 바킹독 문제 모음집 등에서도 볼 수 있는 만큼 매우 유명한 문제이며 풀이도 여러 방법이 있습니다. 

 

분할 정복, 세그먼트 트리 등등의 여러 방법도 있지만 그래도 제일 유명한 풀이는 스택 풀이입니다. Monotone Stack 테크닉을 통해서 스택에 필요한 정보들만 남겨서 푸는 방법인데, 이렇게 풀면 O(N)으로 풀 수 있다고 알려져 있습니다. 그런데, 저는 이 문제를 풀면서 왜 이게 O(N)인지가 궁금했습니다.

 

일단 제 구현 상에서 핵심 아이디어 코드만 따서 보면 이렇게 됩니다.

 

for(int i =0; i<N; i++){
    while(!stck.empty()){
        ll val, idx;
        tie(val, idx) = stck.back();
        if(val > v[i]){
            get<1>(v2[idx]) = i-1;
            get<0>(v2[i]) = get<0>(v2[idx]);
            stck.pop_back();
        }
        else {
            if(val < v[i]){
                get<0>(v2[i]) = idx;
            }
            else get<0>(v2[i]) = get<0>(v2[idx]);
            break;
        }
    } // stack 내부 아이템과 비교
    stck.push_back({v[i], i}); // stack에 현재 아이템 삽입
}

 

 

이제 위의 코드를 보면 알겠지만 제 구현 상에서는, 각 아이템을 한 번씩 볼 때 중간에 while문 등으로 스택 내부에 있는 아이템과 비교하는 작업을 진행합니다. 그렇다면 각 아이템을 한 번씩 볼 때 중간 while 문에서 작업을 여러번이 가능하니 사실 O(N)이 아닐 수 있지 않을까요? while 문 내에서 작업하는 횟수가 유의미하게 커지는 일이 있을 수 있지 않을까요?

 

그런 생각이 들어서 꽤 오랫동안 증명할 방법을 생각해보았는데, 올해 들어서 너무 단순하게 증명이 가능함을 알았습니다. 이제 while 문의 로직 구조를 본다면 아래와 같이 정리가 가능합니다.

 

while(!stck.empty()){
    ll val, idx;
    tie(val, idx) = stck.back();
    if(val > v[i]){ // 현재 스택에 마지막으로 남은 아이템이 불 필요한가?
        get<1>(v2[idx]) = i-1;
        get<0>(v2[i]) = get<0>(v2[idx]);
        stck.pop_back();
    } // 불필요시 pop
    else {
        if(val < v[i]){
            get<0>(v2[i]) = idx;
        }
        else get<0>(v2[i]) = get<0>(v2[idx]);
        break;
    } // 필요시 loop를 끝내고 현재 아이템을 push
}
stck.push_back({v[i], i});

 

이렇게 본다면 while문이 한 번 돌 때마다 스택의 마지막 아이템을 pop 하거나, 아이템을 push 하게 됩니다. 그래서 모든 아이템을 보았을 때 while문이 총 돌아가는 횟수는 아이템들을 최대 몇 번 pop + 최대 몇 번 push 하는 횟수가 됩니다. 각 아이템은 한 번 씩 push 되고, pop이 된 후에는 더 이상 push될 일이 없습니다. 따라서, 각 아이템들은 각각 한 번 씩만 push / pop이 되므로 모든 아이템을 보았을 때 while문에 대한 총 시간복잡도는 O(N)이 됩니다.

 

이렇게 간단하게 증명이 되는 데 왜 이걸 생각하지 못했는지 놀랐습니다. 그래도 이렇게 생각이 나서 글로 정리해보았습니다. 인턴도 이제 슬슬 준비해야하는데 자소서 쓰기 귀찮아서 이렇게 글쓰기 연습이라는 명목하에 글을 써봤습니다 :)