(코딜리티) Lesson 4 : FrogRiverOne - Python

저는 처음에 문제를 이해하는데 너무 오래걸렸네요..

꼼꼼히 안 읽는 습관때문에 너무 어렵게 생각했다가 다시 읽으니 오히려 쉬운 문제 였던 것 ㅠㅠ,,

 

문제 : app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

FrogRiverOne coding task - Learn to Code - Codility

문제 설명

개구리가 강을 건너기를 원한다. 강을 건너기 위해 나뭇잎이 시간에 따라 떨어지는 위치가 담겨있는 N개의 배열 A와 목표 위치인 정수 X를 파라미터로 제공할 것이다.

 

예를 들어,

A = [1, 3, 1, 4, 2, 3, 5, 4]일 경우, X = 5인 경우

1에서부터 5까지 연속된 숫자로 나뭇잎이 다 떨어져 있어야 한다.

0초 -> 1

1초 -> 3

2초 -> 1 (이미 깔려있음)

3초 -> 4 

4초 -> 2

5초 -> 3 (이미 깔려있음)

6초 -> 5

 

이 경우 1에서 5까지 나뭇잎이 다 깔리는 것이고 총 걸린시간은 6초이기에 return은 6을 해야한다.

 

만약, 3초에 4가아닌 3이라면 return은 7초를 해야할 것이다.

또 한, 개구리가 갈 수 없는 경우에는 -1을 return해야 한다. (위 예에서는 1~5 사이에 나뭇잎이 깔리지 않는 경우임)

제한 사항

N과 X는 1~100,000사이의 값

배열 A의 각 요소는 1과 X사이의 값을 갖는다.

코드

 

def solution(X, A):
    
    c = [0]*(X)
    s = 0
    for idx, i in enumerate(A):
        
        if c[i-1] == 0 :
            c[i-1] = 1
            s+=1
            if s == X:
                return idx

    return  -1

해설

1에서 X까지 check를 하기위핸 0을 담은 list c 생성

time을 위한 enumerate의 idx

 

그리고, 처음에는 sum(c)==X를 사용하여 매번 sum을 하면서 N**2의 시간복잡도가 발생했지만, 매번 sum을 피하기위해 if문으로 0인지 아닌지 체크한 후 카운트(s)를 하면서 바로 return할 수 있도록 하여 N의 시간복잡도로 문제를 풀었습니다.