[Codility] Lesson 7. Stacks and Queues - Fish (Python)

문제

• 난이도: Easy

상류와 하류로 향하는 물고기가 있고 각 물고기의 크기에 따라 잡아먹을 때, 남은 물고기의 수를 구하는 문제

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

Fish coding task - Learn to Code - Codility

 

 

풀이

def solution(A, B):
    N = len(A)
    down = []
    alive = 0

    for i in range(N):
        current_size = A[i]
        current_dir = B[i]

        if current_dir == 1:
            down.append(current_size)
        else:
            while down:
                top = down[-1]
                if current_size > top:
                    down.pop()
                else:
                    break

            if not down:
                alive += 1

    return alive + len(down)

 

 

이 문제에서는 같은 방향으로 향하는 물고기끼리는 만나지 않고, 상류-하류로 향하는 물고기가 만난다. 즉, 가장 최근에 하류로 내려온 물고기가 가장 먼저 상류 물고기를 만나게 되는 것이다. 여기에서 스택에 대한 아이디어를 떠올렸다면 쉽게 풀 수 있다.

 

---

EOF.