Contents

[Codility] Lesson7. Stacks and Queues-StoneWall C언어 풀이

   Aug 25, 2020     1 min read     - Comments

1. 문제

k번째 돌벽의 높이를 가지고 있는 H[k]배열이 주어 질 때, 가장 최소한의 돌로 성벽을 쌓는 문제

예제   
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

1

총 7개의 돌로 성벽을 쌓았다.

2. 정답

첫번째 - 100점

$O(N)$

int solution(int H[], int N) {
    int *stack = (int*)malloc(sizeof(int)*N);
    int top = 0, count = 1;
    
    stack[0] = H[0];
    
    for(int i = 1; i < N; i++){
        for(;stack[top] > H[i]; top--){
            if(top == 0){
                stack[top] = H[i];
                count++;
                break;
            }
        }
        if(stack[top] < H[i]){
            count++;
            stack[++top] = H[i];
        }
    }
    return count;
}

  • for(;stack[top] > H[i]; top–)
    H[i] < stack[top]이면 top-- 한다 이 과정을 반복한다.
    top==0이 되면, stack[top] = H[i]가 된다. 이때 돌의 개수가 하나 증가한다.

  • if(stack[top] < H[i])
    H[i] > stack[top]이면 stack[top+1] = H[i]가 된다. 이때 돌의 개수가 하나 증가한다.

  • Skip
    H[i] == stack[top]이면 넘어간다.