[python] Codility Lesson 9-1. MaxProfit

 

easy 태그가 달린것을 보고 가볍게 풀어야지 하다 1시간 넘게 집중하고 눈이 빨게질만큼 빨게져서 해결했다 ㅠㅠ

 

문제에서 핵심이 되는 부분은 max값을 구할때 시간복잡도를 줄이는 것이였다.

 

가령, for문을 돌릴때 i가 3일때 A[3+1 : ]에서 max값을 찾고, 또 i가 11일때 A[11+1 : ] ... and so on...

 

처음 가장 아래에 게시해둔 가볍게 O(N^2)으로 구현해본 코드에서 바로 아래 코드에서 처럼 max값을 구할때 시간복잡도를 줄여 보았다.

 

생각의 흐름은 대충...

 

1. while문을 돌려서 maxList 딕셔너리를 생성하고, max 값의 후보를 키값 index, value값 A[index]로 저장해주자.

 

2. for문을 돌려서 i 보다 key값이 클때 maxval을 업데이트 해주자.

 

허우 짜놓고 보니 정말 엉망진창 코드인건 같아 아쉽다... 실제 코딩테스트때는 이런식으로 구현을 위해서 해결점을 덕지덕지 붙인 코드가 아니게 작성하는 연습을 하자..

 

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

def solution(A):
    # write your code in Python 3.6
    maxProfit = -1
    index = 0
    maxList = dict()
    maxVal = 0
    
    while index < len(A)-1:
        maxVal = max(A[index+1:])
        maxIndex = len(A[:index:-1]) - A[:index:-1].index(maxVal) + index
        maxList[maxIndex] = maxVal
        index = maxIndex


    for i in range(len(A)-1):
        for key, val in maxList.items():
            if key > i:
                maxVal = val
                break

        if maxVal - A[i] > maxProfit:
            maxProfit = maxVal - A[i]
    if maxProfit < 0:
        return 0
    else:
        return maxProfit

 

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

def solution(A):
    # write your code in Python 3.6
    maxProfit = -1
    for i in range(len(A)-1):
        if max(A[i+1:]) - A[i] > maxProfit:
            maxProfit = max(A[i+1:]) - A[i]
    if maxProfit < 0:
        return 0
    else:
        return maxProfit

 

 

조금 더 개선 해보려다 구글링을 통해 잘짠 코드를 살펴보았다 (출처: https://nukeguys.tistory.com/187)

 

너무 최대값에 포커스를 두다 보니 놓친부분이 있었구나 ㅠㅠ

 

아래 코드를 뜯어보면,

 

1. for문을 돌려서 min값을 계속 갱신시켜준다.

 

2. max(0,A[i]-min)으로 profit을 구해준다.

 

3. max(profit, maxProfit)으로 maxProfit을 구한다.

 

어이구 ... 정말 간단하게 O(N) 가능하구나..

 

def solution(A):
    min = 200000
    profit = 0
    maxProfit = 0
    for i in range(1,len(A)):
        if min > A[i-1]: min = A[i-1]
        profit = max(0, A[i]-min)
        maxProfit = max(profit, maxProfit)
    return maxProfit