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

안녕하세요! 오늘도 어김없이 새로운 문제를 풀어서 왔습니다. 오늘 문제는 1차 때 좋은 점수를 맞지 못해서 고민해보고 다시 풀어봤습니다! 1,2차 풀이 모두 작성해보겠습니다! (2-2도 얼른 올리겠습니다ㅠㅠ)

 

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

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

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

---

1. 문제 설명

• A는 N개의 정수들을 가지고 있는 Array입니다. P라는 값은 0과 N사이의 값으로 슬라이싱하는 기준이 되겠습니다.

• 구하고자 하는 값은 index가 0~P-1까지의 합에서 P~N-1까지의 합을 빼서 절댓값한 것의 최솟값입니다.

• 예시

  • A[0] = 3 , A[1] = 1, A[2] = 2, A[3] = 4, A[4] = 3

  • P=1, abs(3-10) = 7

  • P=2, abs(4-9) = 5

  • P=3, abs(6-7) = 1

  • P=4, abs(10-3) = 7

2. 1차 풀이

• idea : for loop로 i값을 기준으로 앞뒤로 잘라서 최솟값보다 작으면 최솟값에 할당하는 방식으로 풀었습니다.

def solution(A):
    min_result = None #최소값이 얼마가 될지 몰라 None으로 입력
    for i in range(1, len(A)):
        A1 = A[:i]
        A2 = A[i:]
        result = abs(sum(A1)-sum(A2))
        if min_result == None or min_result > result: #조건 2개가 자리바뀌면 에러뜸
            min_result = result
    return min_result

• 다음과 같이 풀었으나, 시간 복잡도가 O(N*N)이 되면서 time limit보다 오래 걸리는 현상이 발생했습니다.

• 결론 : 시간 복잡도를 줄여야 한다.

2-1. 1차 풀이 결과

1차 풀이 결과

3. 2차 풀이

• idea : P를 기준으로 왼쪽에 있는 것들은 0부터 첫 원소부터 추가시키고, P 기준으로 오른쪽은 sum(A)를 기준으로 빼주면 for loop로 원소 하나씩만 더해주면 시간 복잡도가 줄어들 수 있을 것이라고 예상했습니다.

def solution(A):
    sum1(A) = 0
    sum2(A) = 0
    min_result = None    
    for i in range(1, len(A)):
        sum1 += A[i-1]
        sum2 -= A[i-1]
        result = abs(sum1-sum2)
        if min_result == None or min_result > result:
            min_result = result
    return min_result

• 위의 코드처럼 짜면 for loop 돌 때마다 sum을 구해야 하는 데, 그 횟수를 줄일 수 있습니다. 시간 복잡도는 O(N)으로 줄어들게 되었습니다.

3-2. 2차 결과 (최종)

2차 풀이 결과

2차 풀이 테스트

• 되는 코드도 중요하지만 불필요한 과정을 줄이고 시간 복잡도를 줄이는 알고리즘을 짜는 것이 중요한 것 같습니다.