[Codility] 7. Stacks, Queues

7.1 Brackets

괄호

def solution(S):
    reverse_c = {')': '(', ']':'[', '}':'{'}
    stacks = []
    for s in S:
        s_ = reverse_c.get(s, -1)
        if s_ == -1: # open
            stacks.append(s)
        else: # close
            if len(stacks) == 0 or s_ != stacks[-1]:
                return 0
            else:
                stacks.pop(len(stacks)-1)
    return int(len(stacks) == 0)

 

7.2 Fish

You are given two non-empty arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

0 represents a fish flowing upstream,
1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

Write a function that, given two non-empty arrays A and B consisting of N integers, returns the number of fish that will stay alive.

 

당신에게는 N개의 정수로 구성된 비어 있지 않은 배열 A와 B가 주어집니다. 배열 A와 B는 강의 흐름을 따라 하류로 정렬된 강에서 N개의 탐욕스러운 물고기를 나타냅니다.

물고기의 번호는 0부터 N - 1까지입니다. 만약 P와 Q가 두 마리의 물고기이고 P < Q라면, P는 처음에는 물고기 Q의 상류에 있습니다. 처음에는, 각각의 물고기가 고유한 위치를 가집니다.

물고기 숫자 P는 A[P]와 B[P]로 표시됩니다. 배열 A는 물고기의 크기를 포함합니다. 모든 요소는 고유합니다. 배열 B는 물고기의 방향을 포함합니다. 그것은 단지 0과 1을 포함합니다. 여기서:

0은 상류로 흐르는 물고기를 나타냅니다,
1은 하류로 흐르는 물고기를 나타냅니다.
만약 두 물고기가 서로 반대 방향으로 움직이고 그들 사이에 다른 (살아있는) 물고기가 없다면, 그들은 결국 서로 만날 것입니다. 그러면 오직 한 마리의 물고기만 살 수 있습니다 - 큰 물고기는 작은 물고기를 먹습니다. 더 정확하게, 우리는 P < Q, B[P] = 1 그리고 B[Q] = 0일 때 두 물고기 P와 Q가 서로 만나고 그들 사이에 살아있는 물고기가 없다고 말합니다. 그들이 만난 후:

만약 A[P] > A[Q]가 Q를 먹고 P는 여전히 하류로 흐르고 있다면,
A[Q] > A[P]이면 Q는 P를 먹고, Q는 여전히 상류로 흐릅니다.
우리는 모든 물고기들이 같은 속도로 흐르고 있다고 가정합니다. 즉, 같은 방향으로 움직이는 물고기들은 절대 만나지 않습니다. 목표는 살아있을 물고기의 수를 계산하는 것입니다.

N개의 정수로 구성된 두 개의 비어 있지 않은 배열 A와 B가 주어졌을 때, 살아 있을 물고기의 수를 반환하는 함수를 쓰시오.

 

def solution(A, B):
    down_stacks = []
    pass_cnt = 0
    for a, b in zip(A, B):
        if b == 1:
            down_stacks.append(a)
        else:
            while len(down_stacks) != 0:
                if down_stacks[-1] < a:
                    down_stacks.pop()
                else:
                    break
            else:
                pass_cnt+=1
    return pass_cnt + len(down_stacks)