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

1. 문제

k번째 물고기의 크기를 가진 A[k]배열과 방향을 가진 B[k] (0은 위로, 1은 아래로 이동)가 있다. 모든 물고기의 속도는 동일하며, 크기가 큰 물고기가 작은 물고기를 잡아 먹을 수 있다.
이때 생존하는 물고기의 수를 반환하는 문제

예제   
A[0] = 4    B[0] = 0
A[1] = 3    B[1] = 1
A[2] = 2    B[2] = 0
A[3] = 1    B[3] = 0
A[4] = 5    B[4] = 0

0번 물고기는 위로 이동중이기 때문에 다른 물고기를 만날 수 없다. 생존 : 1
1번과 2번이 만나면 2번이 잡아먹히게 된다. 생존 : 2
1번과 3번이 만나면 3번이 잡아먹히게 된다. 생존 : 2
1번과 4번이 만나면 1번이 잡아먹히게 된다. 생존 : 2
총 2마리의 물고기가 살아 남게 된다.

2. 정답

첫번째 - 100점

$O(N)$

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

스택에 1방향으로 이동하는 물고기만 입력시킨다. 0방향으로 이동하는 물고기가 나타나면 스택과 비교를 한다. 스택의 크기가 0이 되면 count++시켜준다.