Codility - Fish

물고기가 위 또는 아래 방향으로 헤엄치고 있는데, 

물고기의 사이즈에 따라서 크기가 큰 물고기가 작은 물고기와 충돌할때,

잡아먹게 되면!! 총 몇마리의 물고기가 남는지를 물어보는 문제다

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3.6
    
    if len(A) == 1:
        return 1
    
    arr = []
    
    for i in range(len(A)):
        arr.append((A[i],B[i]))
        
    arr_ = []
    arr_.append(arr[0])

    for i in range(1,len(arr)):
        
        # 충돌하면
        while(True):
            if arr[i][1] == 0 and arr_[len(arr_)-1][1] == 1:
                # 기존 물고기가 더 쎄면
                if arr[i][0] < arr_[len(arr_)-1][0]:
                    break
                # 새로운 물고기가 더 쎄면
                else:
                    del arr_[len(arr_)-1]
            else:
                arr_.append(arr[i])
                break
            
    return len(arr_)
            
    pass

 

처음으로 시도했을때, 정확도는 --> 75%가 나왔다ㅠㅠㅠ

어디서 에러가 발생했는지 확인해보니

모두 한방향으로 가고, 하나의 물고기가 다른 방향으로 갈 때,

Runtime Error가 발생하고 있었다.

 

 

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3.6
    
    if len(A) == 1:
        return 1
    
    arr = []
    
    for i in range(len(A)):
        arr.append((A[i],B[i]))
        
    arr_ = []
    arr_.append(arr[0])

    for i in range(1,len(arr)):
        
        # 충돌하면
        while(True):
            if arr[i][1] == 0 and arr_[len(arr_)-1][1] == 1:
                # 기존 물고기가 더 쎄면
                if arr[i][0] < arr_[len(arr_)-1][0]:
                    break
                # 새로운 물고기가 더 쎄면
                else:
                    del arr_[len(arr_)-1]
                    if len(arr_) == 0:
                        arr_.append(arr[i])
                        break
            else:
                arr_.append(arr[i])
                break
            
    return len(arr_)
            
    pass

 

 

생각해보니 del 이라는 예약어를 사용할 때,

더이상 기존에 물고기가 존재하지 않을 수도 있는 예외처리를 진행해주어야 했다.

 

 

그래서 

del 이라는 코드 아래에 아래와 같이 조건문을 넣어주어 해결하였다.

 

if len(arr_) == 0:
	arr_.append(arr[i])
    	break

 

반복문 하나만 사용하여 문제를 풀었다.

 

시간 복잡도: O(N) --> 100%의 정답률

 

 

관련 유튜브 강의도 있습니다~~!

https://www.youtube.com/watch?v=pPk-qrvBNO8

 

저의 강의입니다ㅋㅋㅋ