주식가격 (Programmers 42584)

🧑‍💻 문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

🧑‍💻 해결방법

• 카테고리에 따라 stack으로 접근했다.
• 처음에는 굳이 stack으로 풀어야할 필요가 있을까? 라는 의문이 생겼으나 시간복잡도, 메모리활용도를 고려했기에 stack으로 분류되었을 것이라고 판단했다.

🧑‍💻 코드

def solution(prices):
    # 주식이 떨어지지 않았을 경우를 가정한 return 값
    remain_second = [len(prices) - 1 - i for i in range(len(prices))]

    # prices의 index 값을 저장해둘 리스트
    stack = [0]

    # 스택과 비교를 위해 0이 아닌 1부터 시작한다.
    for i in range(1, len(prices)):
        # 계속해서 pop을 해줄 것이기에 존재여부로 while을 돌린다.
        while stack:
            index = stack[-1]
            if prices[index] > prices[i]:
                # 값을 비교하고 그 차이에 해당하는 초를 구해서 넣는다.
                remain_second[index] = i - index
                # 제거
                stack.pop()

            else:
                break
        # stack에 새로운 인덱스 값 설정
        stack.append(i)
    return remain_second

🧑‍💻 총평

• 어렵다. 많이 어려웠다.
• 구글링으로 참고를 매우 많이했다.
• 다행히 이해가 어렵지는 않았으나 문제에 대한 이해, 즉 리턴값에 대한 이해가 부족했다. (이 부분은 La Piscine 기간에도 항상 느껴왔다. 나의 큰 문제점이다.)
• 처음에는 '중첩반복문을 활용해서 풀 수 있겠다'고 생각했으나 시간복잡도, 효율성을 고려하면 중첩반복문은 상당히 좋지 않음을 알 수 있다.
• 어제보다 효율성에 대한 고려, 파이썬스러운 사고가 늘고있음을 오늘 느꼈다.
  좀 더 힘내보자!