FrogRiverOne - Easy (Codility, Counting Elements)

def solution(X, A):
    sig = [0] * X
    s = 0

    for i in range(len(A)):
        if sig[A[i]-1] == 0:
            sig[A[i]-1] = 1
            s += 1
            if s == X:
                return i
    return -1

문제를 이해하는데 한참 걸린 문제다. 

 

X에 가는데 걸리는 가장 빠른 초를 찾는 것으로 조건은 return한 초에 X까지 모든 수를 조회해야 한다는 것이다.

 

즉, 1 3 2 5 인데 X가 5면 -1을 리턴해야한다.

 

만약 주어진 X가 4고 A 배열이 2 1 2 3 3 3 4 2 라고 가정하자.

 

sig = [0,0,0,0]이 될테고

s=0으로 시작한다.

 

먼저 0번 인덱스인 2는  sig[2-1]을 1로 변경하고 s를 1 증가시킨다.

그리고 1번 인덱스인 1은 sig[1-1]을 1로 변경하고 s를 1 증가시킨다.

이 과정을 반복하면 반복되는 3은 s가 한 번만 증가하고 4에 도달했을때 s==X가 되어 4의 인덱스인 6이 반환된다.

sig가 X와 길이가 같은 이유가 이것이다. 

결국에는 X의 길이만큼 모든 수가 카운팅이 되어야하고 s==X가 되지 않는다는 것은 값 중 하나가 모자라다는 뜻이다.

그리고 중복은 넘어가기에 인덱스의 위치는 증가하여 정확한 답을 리턴할 수 있다.