[codility] Lesson 3 | PermMissingElem - 파이썬(Python) | Time Complexity

https://app.codility.com/programmers/lessons/3-time_complexity/

3. Time Complexity lesson - Learn to Code - Codility

코딜리티 lesson 3 시간 복잡도에 관련된 문제를 풀었다.

 

리스트 A의 원소는 1부터 N+1까지의 수로 구성되어 있는데 이 중 하나의 숫자가 누락되어 있으며 이때 누락된 숫자를 찾는 문제이다.

---

 

첫번째 시도 - 실패

def solution(A):
    answer = ''

    A = sorted(A)

    for i in range(len(A) -1) :
        if A[i+1] - A[i] != 1 :
            answer = A[i]+1

    return answer

리스트 A를 정렬하여 앞의 원소와 1보다 큰 차이를 보이면 반환하도록 for문을 사용했는데 아래와 같이 case에서도 왕창 실패했다. 오히려 시간 복잡도 부분에서는 한 개의 경우에만 초과되었다.

케이스는 다 틀려놓고 큰 수에 대해서는 맞다니.. 🤦‍♀️

 

두번째 시도 - 성공

해당 문제를 다르게 풀 수 있는 방법을 곰곰히 생각해 보았고 for문을 사용하지 않고 수학적으로 계산을 할 수 있을 것 같았다.

누락되지 않은 가상의 리스트를 만들어 그 리스트의 총 합과 누락된 리스트의 총 합을 빼는 방법을 시도했다.

def solution(A) :
    
    Sum = sum(A)
    
    full_sum = sum(range(1, len(A) +2))
    
    answer = full_sum - Sum
    
    return answer

Sum은 누락된 리스트의 총 합이고 full_sum은 누락된 수를 포함하여 다 더한 값이다.

이 두 총 합을 빼면 누락된 수를 구할 수 있다.

몰랐는데 이렇게 내가 푼 풀이가 어떤 시간 복잡도를 가지는지도 알려주더라.. 뒤늦게 알아차리고 함께 캡쳐했다 ㅎ

---

해당 문제 풀이

GitHub - YOOHYOJEONG/algorithm_practice: 알고리즘 공부 및 코딩테스트 준비