[Codility] FrogRiverOne

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/start/

개구리 강 건너는 문제

숫자 X와 리스트 A가 주어지고, 주어진 리스트 A에 1~X 가 모두 나오는 최소 step을 구한는 문제 (1~X 중 하나라도 없으면 -1 리턴)

나의 첫 번째 풀이

리스트A의 범위가 1 ~ 10만이기 때문에 O(N)의 방법을 찾아야 했다.
내가 생각한 방법은 1~X의 합을 구한 뒤, 각 숫자가 최초로 나올 시에만 A의 원소만큼 빼주어 합이 0이 되면 원소가 모두 나왔다고 가정하고 해당 인덱스를 반환하는 방식으로 풀었다.

def solution(X, A):
    # write your code in Python 3.6

    all_sum = sum(range(X+1)) # 1~X의 합

    river_step = [0 for _ in range(X)]
  
    for i in range(len(A)):
        if river_step[A[i]-1] == 0:
            all_sum -= A[i]
            if all_sum == 0:
                return i
            river_step[A[i]-1] = 1

    return -1

    pass

결과는 O(N)이 나오긴 했지만 더 깔끔한 방법이 무조건 있다고 생각하였다.

나의 두 번째 풀이

두 번째 풀이는 set와 enumerate() 함수를 사용하였다.
set는 중복을 허용하지 않기 때문에 같은 수를 아무리 add해도 원소 자체는 그대로이다.
enumerate()는 순서가 있는 자료구조의 인덱스와 원소값을 리턴해주기 때문에 더 깔끔한 for문을 작성할 수 있다.

def solution(X, A):
    # write your code in Python 3.6

    num_set = set()

    for index, value in enumerate(A):
        num_set.add(value) # 매 반복마다 쓸 데 없이 add를 해주긴 하지만 O(N)는 변하지 않는다.
        if len(num_set) == X:
            return index

    return -1
    pass