List에서 두 원소와 두 원소 사이의 길이를 합을 cost로 할때 최대값 구하기

간단한 문제 풀일이 있었습니다.

List가 있을 때,

value1 + value2 + abs(index(value1) - index(value2))

의 최대값을 구하는 문제!

그냥 전부 다 해보는 취지로 다음과 같이 처음에 접근했습니다.

    def oriSolution(self, A):
        r = -1000000001
        l = len(A)
        if l == 1: # length is 1
            return 0

        for P in range(l):
            for Q in range(P+1, l):
                t = A[P] + A[Q] + (Q-P)
                r = max(r, t)
        return r

특별할 부분은 없는데, O(n^2) (등차수열의 합이니 아마)의 연산비용이 나오는게 영 꺼림직 해서 고민을 좀 해봤습니다.

현재의 최대값인 r(그러고보니 변수 이름이 적절하지 않네요)을 갱신하는 알고리즘인데,

안쪽의 Loop를 생략 할 수 있는 case가 생길 것 같았습니다.

우선 cost는 위에 기술된 것처럼 A[P] + A[Q] + Q-P (항상 양수) 로 기술됩니다.

현재의 최대값이 만약 A[P] + A[Q] + Q-P 에 의해 갱신이 되는 경우에만 안쪽 loop가 유효 하겠죠.

때문에 이걸 생략 할 수 있는 case를 만들었습니다.

현재의 최대값을 curMax 라고 하면,

curMax <= A[P] + A[Q] + (Q-P) 이면 의미가 있습니다.

이는,

curMax - A[P] - (Q-P) <= A[Q] 

으로 표현이 가능한데요, 만약 Q를 확인하지 않아도 이를 만족하지 않음이 자명하다면 안쪽 loop는 생략해도 괜찮습니다.

이를 위해 최대값을 미리 구해둡니다. (max(A)인데 O(n)의 비용으로 구해집니다. 1번만 하면 되므로 그리 큰 비용은 아닙니다)

curMax - A[P] -(Q-P) 가 만약 리스트 전체에서 가장 큰 값보다 크다고 하면, 

즉, curMax - A[P] - (Q-P) > maxValue 이면

curMax - A[P] -(Q-P) <= A[Q]

는 언제나 틀립니다.

따라서 curMax - A[P] - (Q-P) > maxValue 인 경우는 안쪽 Q loop는 돌지 않아도 됩니다.

여기서 Q-P 계산에 Q 가 사용되어서 문제인데,

Q-P의 최대값은 List의 길이를 넘지 않으므로 그냥 l로 치환합니다. 이렇게 해도 논리적 흐름에는 영향이 없으므로 괜찮습니다.

코드는 이렇습니다.

    def betterSolution(self, A):

        r = -1000000001

        l = len(A)

        if l == 1: # length is 1

            return 0

        maxV = max(A)

        for P in xrange(l):

            if r - A[P] - l > maxV:

                continue

            for Q in xrange(P+1, l):

                t = A[P] + A[Q] + (Q-P)

                r = max(r, t)

        return r

별거 아닌 변화 같지만, random한 case에서 속도 향상이 유의미 하네요.

        A = []

        for _ in range(5000):

            A.append(random.randint(1,1000))

        startTime = time.time()

        self.assertTrue(P().betterSolution(A))

        print("{0}: {1}".format("Better", time.time() - startTime))

        startTime = time.time()

        self.assertTrue(P().oriSolution(A))

        print("{0}: {1}".format("Ori", time.time() - startTime))

        self.assertEquals(P().oriSolution(A), P().betterSolution(A))

와 같은 test code에서

Better: 0.205455064774

Ori: 1.86105298996

의 결과가 나오네요.

혹시 잘못생각한 부분이 있다면 comment 주세요 :)