[Codility] Lesson4 FrogRiverOne 풀이 Python
OnlineJudge

[Codility] Lesson4 FrogRiverOne 풀이 Python

반응형

 

문제로이동

 

FrogRiverOne coding task - Learn to Code - Codility

Find the earliest time when a frog can jump to the other side of a river.

app.codility.com


목차

     



    문제 설명

    solution 함수에 X, A 값이 주어집니다.

    개구리가 강을 건너기 위한 최소한의 시간을 출력하는 문제입니다.

    개구리의 초기 위치는 index 0이며, X 위치까지 도달하기 위해서는 반드시 모든 위치에 낙엽이 떨어져야 합니다.

    바로 예시를 보겠습니다.

     

    A[0] = 1

    A[1] = 3

    A[2] = 1

    A[3] = 4

    A[4] = 2

    A[5] = 3

    A[6] = 5

    A[7] = 4

     

    위와 같이 매 시간별 낙엽이 떨어지는 위치가 주어지고 개구리는 X=5까지 도달해야 합니다.

    이 때, 1-2-3-4-5 위치에 모두 낙엽이 존재해야하며, 한번 떨어진 낙엽은 사라지지 않습니다.

    접근 방법

    한번 떨어진 낙엽은 사라지지 않는다 => Visited 배열로 방문처리를 해줍니다.

    매 번 낙엽이 떨어질 때, O(N)만큼의 탐색을 반복하면 시간초과가 발생할 것 입니다. N은 최대 10만번이니까요.

    그래서 낙엽이 새로 떨어질 때(낙엽이 없는 공간) X를 1만큼 감소시켜 X가 0이 되는 순간 정답을 출력합니다.

    X가 0이 됐다는 것은 1부터 X까지 낙엽이 모두 떨어졌다는 뜻이기 때문입니다.

     

    만약 A 배열을 모두 탐색했다면, X까지 모든 낙엽이 떨어지지 않았다는 뜻이기 때문에 -1을 출력합니다.

     

     

     


    소스 코드

    Python

    def solution(X,A):
        visited = [0]*100001
        sec = 0    
        for i in range(len(A)):
            sec+=1
            if not visited[A[i]]:
                visited[A[i]]=1
                X-=1
                if not X:
                    return sec-1
        return -1
    print(solution(5, [1, 3, 1, 4, 2, 3, 5, 4]))

    Java8

    #
    반응형