Codility - fish (Stacks and Queues) [Python]

 

 

 문제

 

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

Fish coding task - Learn to Code - Codility

 

 

 

 

 

 

 문제 상황

 

- 물고기의 크기 리스트와 방향 리스트가 주어진다. 큰 물고기가 작은 물고기를 잡아먹고 최종적으로 살아남은 물고기의 수를 카운팅한다.

 

 

 

 

 

 

 해결 전략

- 전체 물고기를 순회하며 주어진 조건을 연산한다. 상행 물고기들을 모을 스택을 만든다. 

 

 

 

 

 

 

 코드

 

def solution(A: list, B: list) -> int:
    upstreamFish = []
    fishNumber = 0
    for i in range(len(A)):
        if B[i]: # fish is upstreaming
            upstreamFish.append(A[i])
            continue
        while True:
            if not upstreamFish:
                fishNumber += 1
                break
            if upstreamFish[-1] < A[i]:
                upstreamFish.pop()
                continue
            break
    fishNumber += len(upstreamFish)
    return fishNumber
 

 

 

 

 

 

 

 

 

 해설

 

- O(N)의 속도가 나온다. 중요한 것은 상류로 올라가 살아남은 물고기도 계산해야 하는 것이다. upstreamFish에 남은 물고기가 있다면 상류에 살아남은 물고기가 있으므로 마지막에 더해주어야 한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 문제를 이해하기가 어려웠다. 확실히 codility는 문제가 엄밀하게 정의되어 있지 않다.

 

- 실수 첫번째는 upstreamFish를 리스트가 아닌 하나의 int로 정의한 것이다. 문제가 발생할 수 있다.

 

- 실수 두번째는 상류로 향해 살아남은 물고기의 수를 더하지 않았다는 것이다.

 

- for문 안에 while문이 있기 때문에 O(N*M) 여기서 M은 len(upstreamFish)로 생각했지만 실제로 이 upstreamFish는 비워지고 채워지고를 반복해서인지 길이가 계산되지 않아 O(N)으로 되었다.