[Codility] Lesson4 FrogRiverOne 풀이 Python

 

문제로이동

FrogRiverOne coding task - Learn to Code - Codility

---

목차

 

---

---

문제 설명

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

#