[ Codility 코딜리티 ] Lesson 4 FrogRiverOne Python 파이썬 풀이

 

 

// 문제 요약

 

위치 0에서 폭이 X인 강을 건너

위치 X+1인 강의 반대쪽으로 가고자하는

개구리가 있다.

강물의 흐름을 무시할 수 있고

나뭇잎이 강 위로 떨어진다고 할때

(한번 떨어진 잎은 사라지지 않는다고 할때)

시간 K때 떨어진 나뭇잎의 위치는 A[K]이고

A는 N개의 정수로 구성된 비어있지 않은 배열이다.

1에서 X까지 모든 위치가 잎으로 채워지면

개구리가 건너갈 수 있다고 할 때

개구리가 강을 건널 수 있는

가장 빠른 시간을 구해라.

개구리가 강을 건널 수 없을 경우 -1을 return해라.

 

 

 

// 문제 풀이

 

문제가 복잡하다.

하지만 간단하게 생각할 경우

"X 가 주어지면

1에서 X까지 한번 이상 등장하는

가장 작은 K를 구해라"

로 문제가 요약된다.

 

이렇게 핵심만 남기는 것이

실재로 개구리가

강을 이동하는 모습을 상상하는 것보다

훨씬 풀이가 쉽다.

 

요약된 문제의 경우

A를 하나씩 빼보면서

새로 등장한 원소면 추가하고

아니면 그대로 지나가는 식으로

생각할 수 있다.

 

 

 

코드를 먼저 보자.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import collections

def solution(X, A):
    # write your code in Python 3.6
    count = collections.defaultdict(int)

    for i, n in enumerate(A):
        count[n] = i
        if len(count) == X:
            return i

    return -1

 

이번에는 collections 안에 있는

defaultdict()를 사용했다.

 

defaultdict()는 딕셔너리의 key가 없을 경우

어떤 default value 를 value로 하여

맵핑을 생성하는 딕셔너리를 말한다.

 

이때 괄호안에는 callable 한 객체가 들어가야하며

즉 function 이나 callable class가 들어가야하며

key로는 어떤 것도 상관없다.

 

 

 

왜 in을 쓰지 않고 이러한 방식으로 했을까?

a in A의 경우

a가 있는지 없는지 알아보기 위해서는

A의 모든 원소를 다 들여다보아야 한다. 

즉, O(n)의 시간복잡도를 가지게 된다.

따라서 O(n)의 for문 안에서 in을 쓰면

O(n*2)가 되어서 실패할 확률이 높아진다.

 

하지만 이미 count되고 있는

딕셔너리의 key라면 O(1)의

해쉬맵핑으로 접근할 수 있기 때문에

O(n)의 시간복잡도를 유지할 수 있다.

 

for문이 끝까지 다 돌았는데도

모든 숫자가 다 등장하지 않으면

-1을 return하도록 한다.

 

X가 1인 경우 무조건 건너갈 수 있기 때문에

if로 처리해주는 것도 하나의 방법일 수 있겠다.