[ Codility 코딜리티 ] Lesson 3 TapeEquilibrium Python 파이썬 풀이

 

 

// 문제 요약

 

비어 있지 않고

N개의 정수로 이루어진

배열 A가 주어질때

A가 한 테이프를 따라 매겨진 번호라고 하자.

 

0과 N 사이의 정수 P가 주어지면

A[0 ~ P-1], A[P ~ N-1] 으로 테이프를 나눈다고 할때

나누어진 두 테이프에 매겨진 값을

각각 모두 더하여 얻어진 두 값의

가장 작은 absolute difference는 얼마인가?

 

 

 

// 풀이

 

이런 문제는 자칫 영어가 꼬이면

문제를 이해하는데 시간을 낭비하고 만다.

따라서 꼼꼼하게 차근차근

본문을 잘 읽어서 문제를 정확하게 이해해야 한다.

 

우선은 p를 옮겨가면서

p가 옮겨질때마다 양쪽을 모두 더하는 경우로

생각하기 쉬우나

그렇게 되면 p를 옮기기위해 N번

그리고 임의의 p에서 덧셈을 N번

하는 경우기 때문에 O(N**2)이 된다.

 

코딩문제의 정답으로는

많아도 O(N)정도를 생각하는 것이 좋다.

생각해낸 답변이 논리상 O(N**2)가 나온다면

더 좋은 방법은 없는지 다시 생각해 보아야 한다.

 

 

 

코드를 먼저 보자.

 

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

def solution(A):
    # write your code in Python 3.6
    left, right = 0, sum(A)

    min_dist = sys.maxsize
    for n in A[:-1]:
        left, right = left + n, right - n
        min_dist = min(min_dist, abs(left - right))

    return min_dist

코딜리티에서는 sys모듈도 제공한다.

min or max 문제에서는

처음 비교할 대상을 어떻게 선정할지

난감한 경우가 있는데 그땐 일반적으로

min을 구해야한다면 sys.maxsize를

max를 구해야한다면 -sys.maxsize를 기준으로

비교를 시작해야한다.

 

코딜리티의 거의 모든 문제들은

주어지는 수의 범위가 함께 있으므로

그 범위의 가장 큰 값이나

가장 작은 값을 써도 무방하지만

실무에서는 값의 입력이 어떤 범위를 따르는지

알기 힘들때가 종종있다.

 

따라서 임의의 수를 지정하는 방식보다는

시스템의 최대/최소값을 쓰는 것이

오류를 방지할 수 있는 좋은 방법이다.

 

 

 

이번 풀이는 Lesson 3 Time Complexity에 속해 있지만

어떤 관점으로 본다면 Prefix Sums에 들어갈 수도 있다.

미리 배열의 합을 모두 구해서 : O(N)

그 합으로부터 일정 범위를 빼면서 : O(N)

값을 찾아내면

O(N**2) 을 O(N+N)으로 낮출 수 있다.

계수는 일반적으로 생략하므로

O(N)의 풀이를 얻을 수 있다.

 

역시 시번에도 절대값을 구하는 내장함수

abs()를 이용해서 문제풀이를 진행하였다.

 

assumptions를 확인해도

이렇다할 위험요소가 없으므로

예외처리를 해줄 필요가 없다.