[Codility] FrogRiverOne

0. 문제

position 0에 있는 개구리가 하나 있다.

이 개구리는 X를 이동하여 X+1의 위치로 이동하고 싶어한다.(그러니까 A[0]에서 A[X+1]로 이동한다는 거)

리스트 A는 개구리가 건널 수 있는 잎의 위치리스트다.

배열의 index는 초(second)이고, value는 나뭇잎이 놓이는 위치이다.

그러니까, 개구리가 5로 이동하고 싶은데 리스트 A가 [1, 3, 1, 4, 2, 3, 5, 4] 면 6초가 지나야 개구리가 원하는 위치로 갈 수 있다는 거.

만약 배열이 [1, 3, 1, 3, 4] 이라면 개구리는 원하는 곳에 가지 못하고, 이럴 땐 -1을 리턴해야 한다.

X와 A가 파라미터로 주어질 때, 개구리가 원하는 위치로 이동할 때까지 걸리는 시간을 구하라.

1. 답변

문제를 처음에 잘못 이해해서 빵점이 나왔다ㅋㅋㅋㅋ

다시 읽고 충분히 이해한 후에 풀었더니 이번엔 반타작.

def solution(X, A):
    target = A.index(X)
    for i in range(target, len(A)):
        if len(set(A[:i+1])) == X:
            return i
    return -1

correctness는 100%이나 time complexity는 빵점. O(N)이어야 하는데 O(N**2)이 나왔다.

loop문을 돌면서 매번 리스트 A를 set()으로 묶었기 때문이다!

리스트를 set()하면 O(N)인데 이걸 리스트만큼 loop로 돌렸으니 O(N**2)!! 우웩!!

그래서 set() 사용은 유지했으나 이번엔 하나씩 add()하는 식으로 수정!

add()는 time complexity가 O(1)이므로 loop문을 돌면 O(N) 혹은 그 이하의 시간이 소요된다.

def solution(X, A):
    leaf_set = set()
    for idx, val in enumerate(A):
        leaf_set.add(val)
        if len(leaf_set) == X:
            return idx
    return -1