[Easy] Fish

[문제]

서로 움직이는 방향이 다른 물고기들이 마주쳤을 때 물고기 크기에 따라 작은 물고기는 죽고 큰 물고기만 살아남을 때 전체적으로 살아남는 물고기 수를 세는 문제

Fish coding task - Learn to Code - Codility

 

[코드]

Stack에 downstream으로 움직이는 물고기를 담고 크기를 비교하여 살아 남는 물고기 수를 카운팅 함

시간복잡도 : O(N)

def solution(A, B):
    # write your code in Python 3.6
    fish = []
    answer = 0
    for idx, f in enumerate(A) :
        if B[idx] == 1 :
            fish.append(f)
        else :
            while fish :
                if fish[-1] > f :
                    break
                else :
                    fish.pop()
            if not fish :
                answer += 1
                    
    return answer + len(fish)