Codility - FrogRiverOne[Python]

😅 문제 

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

🤔 문제 상황 

- 문제 이해가 너무너무 어려운 문제였다.

 

- 둑을 건너기 위해, 예를 들어 거리가 5인 둑이라면 낙엽이 1, 2, 3, 4, 5 모두에 낙엽이 있는 최소 시간을 구하는 문제이다.

 

🧐 해결 전략 

- 배열을 선언해 그 수가 나오면 0으로 초기화 하는 방식으로 한다.

🎰 코드 

def solution(X, A):
    ck = [i for i in range(X+1)]
    cnt = 0
    for k in range(len(A)):
        if A[k] < X+1:
            if ck[A[k]] != 0 :
                ck[A[k]] = 0
                cnt += 1
            if cnt == k:
                return k
    return -1
    
    
 

https://colorscripter.com/

🧙‍♂️ 해설

- 처음 생각했던 것은 dict를 선언하는 것이었는데 key랑 value 정하기도 애매하고 굳이 dict를 할 이유는 없었다. 

 

- 만약 X가 너무 커지면 위의 방법은 사용할 수 없다. (메모리 이슈)

📈 새로 학습한 것 & 실수 

- 중복이 제거된 리스트의 길이를 구하려고 len(list(set())) 를 for문 안에 조건으로 돌렸더니 n**2의 속도가 나왔다. 그래서 cnt= 0 을 넣어서 cnt == X 조건으로 바꿨다. 조금만 더 생각하면 효율적으로 바꿀수 있다. ==> O(N)로 바뀌었다.