Lesson7. Stacks and Queues - Fish

Fish - N voracious fish are moving along a river. Calculate how many fish are alive.

https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

문제요약

배열 A와 B가 주어진다. A[i]는 i번째 물고기의 크기를 의미하고 B[i]는 i번째 물고기의 방향(0은 왼쪽, 1은 오른쪽)을 의미한다.

P < Q 일 때, A[P]와 A[Q]사이에 물고기가 없고 B[P] = 1, B[Q] = 0이면 두 물고기는 만나게 되고 큰 물고기가 작은 물고기를 잡아먹는다.

모든 물고기는 같은 속도로 움직이고, 따라서 같은 방향의 물고기는 만나지 않는다. 최종적으로 살아있는 물고기의 수를 계산한다.

Assume that:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [0..1,000,000,000];

each element of array B is an integer that can have one of the following values: 0, 1;

the elements of A are all distinct.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

간단한 접근으로 오른쪽으로 가는 물고기는 stack에 넣고 왼쪽으로 가는 물고기를 만나면 stack에서 하나씩 꺼내서 크기를 비교한다. 왼쪽으로 가는 물고기가 더 크면 stack에서 꺼내서 크기 비교를 반복한다. 만약 stack에서 꺼낸 오른쪽으로 가는 물고기가 더 크면 다시 stack에 넣고 다음으로 물고기에 대해 확인한다. 추가 적으로 고려할 상황은 stack이 비었을 경우에는 해당 물고기를 stack에 그냥 넣어주고, 이렇게 되면 stack에 왼쪽으로 가는 물고기도 들어가게 되므로 꺼내서 비교시 방향을 같이 확인해준다. 꺼냈을 때 오른쪽으로 가는 물고기일 경우 크기 비교를 하되, 왼쪽으로 가는 물고기일 경우에는 둘 다 stack에 넣어 준다. 전체에 대해 처리하고 나면 stack에 남아있는 물고기가 최종 살아있는 물고기가 된다.

정리하면, stack이 비어있거나, 오른쪽으로 가는 물고기이거나, 현재 stack의 top에 왼쪽으로 가는 물고기가 있으면 stack에 추가하고 다음으로 넘어간다. 왼쪽으로 가는 물고기이면서 stack의 top에 오른쪽으로 가는 물고기가 있으면 크기 비교를 해서 왼쪽으로 가는 물고기가 크면 stack에 대해서 반복하고, 오른쪽으로 가는 물고기가 크면 stack에 그대로 유지하고 다음 물고기에 대해서 진행한다.