[TIL] 프로그래머스 - 주식 가격 / Leetcode - Trapping Rain Water 😣

[Today I Learned]

# 프로그래머스 - 주식 가격

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

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

 

@solution.py

스택 써서 매뉴얼 하게 푸는 건 금방 캐치했는데, 코드로 세팅하기까지가 오래 걸렸던 문제 : /

def solution(prices):
    
    prices = [(p,i) for i,p in enumerate(prices)]
    stack = []
    answer = [0] * len(prices) # stack
    
    for p in prices:
        if not stack or stack[-1][0] <= p[0]:
            stack.append(p)
        else:
            while stack and (stack[-1][0] > p[0]):
                pop = stack.pop()
                answer[pop[1]] = p[1] - pop[1]
            stack.append(p)
    
    while stack:
        pop = stack.pop()
        answer[pop[1]] = p[1] - pop[1]
            
    return answer

stack이 비어있지는 않은지 조건을 추가해줘야 한다는 점이랑 마지막에 prices 반복문은 끝났어도 stack이 차있다면 연산을 계속해줘야 하는 점을 Key였음!

여기서 다른 사람들 코드를 보다보니... stack.append(p)는 어차피 무조건 이뤄지는 과정이고, 그 전에 pop을 할 원소가 있는지만 체크하면 된다는 점을 깨달았고 아래처럼 코드를 개선할 수 있었다.

def solution(prices):
    
    prices = [(p,i) for i,p in enumerate(prices)]
    stack = []
    answer = [0] * len(prices) # stack
    
    for p in prices:
        while stack and (stack[-1][0] > p[0]):
                pop = stack.pop()
                answer[pop[1]] = p[1] - pop[1]
        stack.append(p)
    
    while stack:
        pop = stack.pop()
        answer[pop[1]] = p[1] - pop[1]
            
    return answer

 

# Leetcode - Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

@solution.py

대략적인 방향은 금방 캐치했는데, 물 양을 어떻게 계산할지 일반화하는 것이 어려웠다. 남자친구 도움을 받고 받아 최종 정리한 코드는 아래와 같다.

# Trapping Rain Water - △△△

class Solution:
    def trap(self, height: List[int]) -> int:
    
        stack = [height[0]]
        max = height[0]
        volume = 0

        for h in height[1:]:

            stack.append(h)

            if h >= max:
                for t in stack[1:-1]: # 1:-1
                    volume += max-t

                max = h
                stack = [h] # stack.append(h)

        if stack: # stack이 차있다면
            height = stack.copy()
            height.reverse()

            stack=[height[0]]
            max = height[0]

            for h in height[1:]:

                stack.append(h)

                if h >= max:
                    for t in stack[1:-1]:
                        volume += max-t

                    max = h
                    stack = [h]

        return volume

스택에 쭉 height를 추가하다가 지금까지 저장된 height보다 더 큰 height를 만나면 stack에 저장된 height 값들을 대상으로 쭉 volume 값을 계산하는 방법이다.

가장 처리가 어려웠던 부분은 지금까지 저장된 height보다 더 큰 height를 만나지 않고 height list가 끝나는 경우였다. 그 경우에는 무조건 stack에 값들이 남아있기 때문에 if stack으로 추가 처리를 할 수 있게 했다. 그런데 이 때 이 stack을 reverse해주면 위에서 사용했던 방법을 그대로 사용할 수 있다는 점! 이걸 캐치하기까지 시간이 굉장히 오래걸렸다. 

이 외에도 if h>= max 조건문에 걸렸을때, max값은 무조건 stack의 0번째 원소가 된다는 점 등을 간과해서, 코드를 불필요하게 지저분하게 짰었다. 😅

이 문제는 파이썬 알고리즘 인터뷰라는 책에 실려있기도한데, 투포인터와 스택을 이용해 풀이했다. 다음은 스택을 이용한 코드. 

def trap(self, height: List[int]) -> int:
	stack = []
	volume = 0
    
	for i in range(len(height)):
 		while stack and height[i] > height[stack[-1]]:
			top = stack.pop() 
            
        if not len(stack):
            break

		distance = i - stack[-1] - 1
		waters = min(height[i], height[stack[-1]]) - height[top]

		volume += distance * waters

		stack.append(i)

	return volume

아 티스토리 코드블럭 미리보기 인덴트 틀리는거 제발 고쳐줘요 확 velog로 가버릴까보다