[Codility] 코딜리티 4-1. FrogRiverOne (Python)

안녕하세요! 오늘도 새로운 문제를 풀어서 왔습니다! 오늘 문제는 맞추긴 했지만 시간복잡도때문에 100%를 맞추지는 못했습니다. 좀 지나고 다음에 풀어보고 시간복잡도를 낮추면 다시 적어보겠습니다.

 

이전 코딩 내용이 궁금하시다면 아래 링크로 이동하시면 됩니다!

코딜리티 이전 글 - 2020/07/17 - [파이썬] - [Codility] 코딜리티 3-3. TapeEquilibrium (Python)

[Codility] 코딜리티 3-3. TapeEquilibrium (Python)

---

1. 문제 설명

• 개구리가 X 위치에 도착하도록 합니다. A에는 강가에 나뭇잎이 떨어지는 데 index는 시간, 값은 위치를 나타냅니다.
• 결과로 받고 싶은 return값은 X위치까지 가기 위해 1,2,3,4,...,X값이 모두 지나갔을 때의 마지막 값에 대한 index를 추출하는 것이 목표. 만약에 X에 도달하지 못했다면 -1을 추출.

2. 1차 풀이

• idea : A의 값을 하나씩 i로 받아서 해당 원소가 B에 있으면 index만 증가, 해당 원소가 없으면 합을 비교해서 count값 출력

def solution(X, A):
    B=[]
    count=0
    for i in A :
        if i in B:
            count +=1
        else:
            B.append(i)
            if sum(B) == sum(range(1,X+1)):
                return count
                break
            count +=1
    return -1

3. 1차 결과

1차 결과

1차 테스트 결과

• 시간복잡도가 O(n**2)이 되어, timeout error가 발생했습니다.
• 추후에 시간복잡도를 줄여서 풀어보고 수정해서 올리도록 하겠습니다.