[python] 프로그래머스 - 주식 가격

 

출처 : 프로그래머스 코딩테스트 연습,  https://programmers.co.kr/learn/courses/30/lessons/42584

 

문제 설명이 왜 다 이렇지.

문제 자체가 좀 어거지로 만든 느낌이 있어서 설명하려고 해도 좀 곤란할 것 같긴 하다.

예제보면서 이해하는게 답인 듯.

 

 

첫 번째 풀이 : 이중 for문

 

def solution(prices):
    answer = []
    for index in range(len(prices) - 1):
        count = 0
        for index2 in range(index + 1, len(prices)):
            if prices[index] <= prices[index2]:
                count += 1
            else:
                count += 1
                break
        answer.append(count)
    
    answer.append(0)
    return answer

 

사고방식은 이렇다.

 

● t초 일 때의 시간이 그 뒤에서 가격이 떨어지는지 보려면

     t초의 가격을 안 상태에서 그 뒤의 시간을 순서대로 보면서 가격을 비교해야한다.

● 만약 가격이 떨어지지 않았다면 count + 1하고 다음 것을 보고

● 가격이 떨어졌다면 count + 1을 하고 for문을 탈출하여 나간다.

● 그다음 t+1 초일 때의 가격과 그 뒤의 가격들을 순차적으로 비교하며 위 반복

 

사실 효율성 테스트가 있어서 O(N^2)이라면 당연히 통과가 안 될 줄 알았는데 놀랍게도 통과가 되었다.

하지만 input의 크기가 커지면 통과가 안 될 듯하다.

그런데 내가 느낀 찝찝함은 다른 사람들도 느끼는지 O(N^2)을 어떻게든 벗어나려고 덧글로 토의를 하더라.

 

 

두 번째 풀이 : 약간의 개선

 

다른 분들 풀이를 보다가 내 코드의 이상한 점을 알았다.

 

if prices[index] <= prices[index2]:
    count += 1
else:
    count += 1
    break

 

이게 지금 맞는 코든가....?

if와 else에서 둘다 count +=1 이라는 코드를 쓰고 있다.

쓸데없이 코드를 중복해서 조건문을 이상하게 쓰고 있는 코드이다.

그렇게 수정한 코드....

 

def solution(prices):
    answer = []
    for index in range(len(prices) - 1):
        count = 0
        for index2 in range(index + 1, len(prices)):
            count += 1

            if prices[index] > prices[index2]:
                break
                
        answer.append(count)
    
    answer.append(0)
    return answer

 

answer 리스트를 처음부터 [0] * len(prices)로 초기화하여

마지막에 answer.append(0)를 해줄 필요가 없는 코드 역시 있었다.

 

---

 

시간 복잡도

 

O(N^2)

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

스택을 이용한 풀이 (출처 : https://gurumee92.tistory.com/170)

 

def solution(prices):
    answer = [-1] * len(prices)
    
    time = 0
    stack = [0] #stack : time을 넣는 stack, top에 가까워질 수록 가격이 올라간다.
    
    for time in range(1, len(prices)):
        prev_price = prices[stack[-1]] if len(stack) > 0 else -1
        now_price = prices[time]
        
        if len(stack) == 0 or prev_price <= now_price:
            #stack이 비었거나 이전보다 가격이 높거나 같다면 stack에 time 넣는다.
            stack.append(time)
        else:
            #현재보다 이전이 높다면 이전 가격이 같거나 작을 때까지 time을 stack에서 뺀다.
            #now_price는 유지한 채 prev_price만 이전으로 거슬러가면서 진행
            
            while len(stack) > 0 and prev_price > now_price:
                prev_time = stack.pop()
                answer[prev_time] = time - prev_time
                prev_price = prices[stack[-1]] if len(stack) > 0 else -1
            
            stack.append(time)
            
    stack.reverse()
    
    while len(stack) > 0:
        time = stack.pop()
        answer[time] = len(answer) - 1 - time
        
    return answer

 

이 코드의 시간 복잡도는 O(N)

로직은 이렇다. 코드는 출처에서 로직만 따와서 코드는 내가 작성함.(그래서 개떡같다)

 

stack에 시간을 넣는다. 이때 stack에는 top에 가까워질수록 가격이 올라가는 시간만 쌓이도록 한다.

즉, 이전 가격 <= 현재 가격이라면 유지한 것이므로 stack에 현재 가격을 넣는다.

반대로 이전 가격 > 현재 가격이라면 유지하지 못한 것이므로 현재 가격보다 큰 시점의 시간을 스택에서 모두 뺀다.

뺄 때, 뺀 시간의 가격의 유지 기간은 현재 시간 - 이전 시간이므로 이를 그 시점의 유지 시간으로 넣는다.

 

로직은 금방 이해했는데 구현이 안됨. 하.........답답해 죽는줄.

일단 문제 카테고리가 스택/큐이고, O(N^2)은 시간 복잡도가 너무 크기 때문에

출제자가 생각한 방향은 위와 같은 풀이일 것이다. 이 풀이의 시간 복잡도는 O(N).

그리고 난 이 풀이 로직을 보고 구현하는데 5일 걸림. 난 바본가.....?

 

 

고찰

 

문제 풀이의 의도가 스택을 사용해서 푸는건데 문제를 보자마자 떠오른 생각은

1초일 때 2초부터 n초까지의 가격과 비교하고, 2초일 때 3초부터 n초까지의 가격과 비교하고....라는...

아주 간단한 로직이 가장 먼저 떠올랐다. 그리고 이 풀이가 O(N^2)인 것 역시 바로 알았지만 다른 로직이 떠오르지 않았다.

 

스택을 이용한 풀이가 구현에 오래 걸린 이유가 구현하는 과정에서

갑자기 이 방법이 더 좋을 것 같은데? 해서 이 방법도 넣어보고 해서 혼란스러웠고,

무엇보다 Index Range Error가 내 멘탈을 와장창깼다. 이전에도 풀면서 가장 많이 등장한 에러가 이 에러이다.

앞으로는 문제를 풀 때 계속 Index Error가 날 만한 부분을 주의 깊게 살펴 보면서 진행해야겠다.

 

예를 들면,

 

answer = [-1] * len(prices)

 

과 같이 answer 리스트를 미리 할당해둔다던가.

 

for time in range(1, len(prices)):

 

과 같은 코드는 time을 참고하는 과정에서 prices가 고정된 리스트이기 때문에 index 에러가 날 이유가 없고

 

for :
        prev_price = prices[stack[-1]] if len(stack) > 0 else -1
        
        if :
        else:
            while len(stack) > 0 and prev_price > now_price:
                prev_time = stack.pop()
                answer[prev_time] = time - prev_time
                prev_price = prices[stack[-1]] if len(stack) > 0 else -1

 

과 같이 stack이 변하는 리스트이기 떄문에 stack의 값을 index를 통해 직접적으로 참고할 때,

혹은 pop()과 같은 성분에 관한 함수를 사용할 때 Index 에러가 날 확률이 높다는 것.

 

정리하면, 

 

● 미리 list를 필요한 크기만큼 할당해서 임의의 index를 참고해도 값이 존재하게 하거나

● 내부의 값이 계속 바뀌는 리스트의 경우에는 index를 참고하거나 성분을 건드리는 함수를 쓸 때,

    어떤 상태에서도 값이 들어오는지 미리 꼼꼼히 체크하거나

● 아니면 리스트의 상태를 최대한 건드리지 않는 상태로 코드를 짜거나

 

정도로 정리해볼 수 있겠다.