[codility] Fish

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

Fish coding task - Learn to Code - Codility

살아있는 모든 fish를 d에 넣었더니 시간초과 하나가 떠서 87프로가 됐다

def solution(A, B):
    # write your code in Python 3.6
    fish = []
    for i in range(len(A)):
        fish.append((A[i],B[i]))
    
    while len(fish) > 0:
        #print(fish)
        d=[(fish[0][0],fish[0][1])]
        pointer = 0
        for i in range(1,len(fish)):
            if d[pointer][1] == 1 and fish[i][1] == 0:
                if d[pointer][0] < fish[i][0]:
                    d.pop()
                    d.append((fish[i][0],fish[i][1]))
            else:
                d.append((fish[i][0],fish[i][1]))
                pointer += 1
        if len(fish) != len(d):
            fish = d
        else:
            return len(fish)
    #    print(d)
    return len(fish)

 

다른 사람 글을 참고해보자 : yceffort.kr/2020/06/codility-07-02-fish

 

d에는 아래로 가는 물고기만 저장해본다

위로 가는 물고기가 나오면 모든 아래로 가는 물고기와 대결해서 위로 가는 물고기가 전부 이기면 -> len(d) == 0

위로 가는 물고기 개수를 세어준다

def solution(A, B):
    # write your code in Python 3.6
    d = []
    count_up = 0
    for fish in zip(A,B):
        if fish[1] == 1:
            d.append(fish)
        elif fish[1] == 0:
            while len(d) > 0:
                prev_item = d[-1]
                if prev_item[0] > fish[0]:
                    break
                else:
                    d.pop()
            if len(d) == 0:
                count_up +=1
        #print(d,count_up)
    return len(d)+count_up

 

와....

울똑똑이는 recursive로 풀었따

근데 python은 recursion limit을 1000으로 해둬서 1000번 이상 recursive를 부르면 에러 처리함.

제한을 늘이려면 sys.setrecursionlimit()을 사용해야 하나봄

import sys
sys.setrecursionlimit(1000000)


class Stack():
    def __init__(self):
        self.top = -1
        self.items = []
    def push(self, item):
        prev_item = self.pop()
        if (prev_item is None ):
            self.items.append(item)
            self.top += 1
        elif (prev_item[1] == 1 and item[1] == 0):
            if prev_item[0] > item[0]:
                self.push(prev_item)
            else:
                self.push(item)
        else:
            self.items.append(prev_item)
            self.items.append(item)
            self.top += 2
        return

    def pop(self):
        if(self.top == -1):
            return None
        else:
            item = self.items.pop()
            self.top -= 1
            return item 


def solution(A, B):

    stack = Stack()

    for item in zip(A,B):
        stack.push(item)
        # print(stack.top)
    
    return len(stack.items)