Lesson 5: StoneWall (Stone Wall)

Lesson 5: StoneWall
https://codility.com/programmers/lessons/5

これはCodilityのブログに解説がありますので、そちらをごらんください。
http://blog.codility.com/2012/06/sigma-2012-codility-programming.html


とはいえ、自分でやってみました。

#include <alloca.h>

int solution(int H[], int N) {
    
    int *stack = (int*)alloca(sizeof(int) * N);
    int sp = 0;

    int cnt = 0;
    
    
    int i;
    for (i = 0; i < N; i++){
        
        //if there is no stone on the left, we need a new stone.
        if (sp == 0){
            cnt++;
            stack[sp++] = H[i];
            //check the next height.
            continue;
        }
        
        //there is at least one stone on the left
        
        //the same hight, we don't need a new stone.
        if (stack[sp - 1] == H[i]){
            //check the next height.
            continue;
        }
        
        //the hight goes up, we need a new stone
        if (stack[sp -1] < H[i]){
            cnt++;
            stack[sp++] = H[i];
            //check the next height.
            continue;
        }
        
        //the hight goes down, try rewinding the stack
        while(1){
                    
            //the stone on the left is still heigher.
            //try rewind the stack.
            if (stack[sp - 1] > H[i]){
                sp--;
                
                //reached the bottom of the stack.
                if (sp == 0){
                    //we need a new stone.
                    cnt++;
                    stack[sp++] = H[i];
                    break;        
                }
                continue;
            }
            
            //there is a stone with the same height on the left.
            //this can continue grow to the right.
            if (stack[sp - 1] == H[i]){
                break;
            }
            
            //the stone on the left is lower than the new height.
            //there is need for a new stone.
            stack[sp++] = H[i];
            cnt++;
            break;
        }
        
    }
    
    return cnt;
}

ですが、Codilityのブログを見ればわかる通り、条件を整理して行くともう少し短いコードにすることができます。まずスタックを巻き戻す動作をするという方針で、if文を整理する感じですね。（とはいうものの、短いコードが常にわかりやすい訳ではありませんが）。これも100%のスコアのを書いておきましょう。

#include <alloca.h>

int solution(int H[], int N) {
    
    int *stack = (int*)alloca(sizeof(int) * N);
    int sp = 0;

    int cnt = 0;
    
    int i;
    for (i = 0; i < N; i++){
        
        //try rewind the stack first.
        while (sp > 0 && stack[sp - 1] > H[i]){
            sp--;
        }
        
        //when the code reaches here, it is always
        //sp == 0 and/or stack[sp - 1] < H[i].
        
        //if there is the stone with the same height, 
        //simply keep on using it!
        if (sp > 0 && stack[sp - 1] == H[i]){
            continue;
        }

        //if not, we need a new stone.
        stack[sp++] = H[i];
        cnt++;
    }
    
    return cnt;
}