[python] leetcode 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/ 

문제 설명

 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라.

문제 접근 및 풀이

[1st Try] - 투 포인터

1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정.
2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다.
3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다.
4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다.
5) T의 마지막 원소는 무조건 0일을 기다리므로, 마지막으로 0을 append한다.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        """
        투포인터로 접근
        """
        left, right = 0, 1
        res = []
        
        while left < len(T)-1:
            if T[left] < T[right]:
                res.append(right-left)
                left += 1 # left pointer 움직임
                right = left + 1 # right pointer 초기화
            else:
                right += 1
                if right >= len(T): # 더 따뜻한 날을 찾지 못했을 경우
                    res.append(0)
                    left += 1
                    right = left + 1
        
        res.append(0) # 어차피 마지막은 0이므로.
        
        return res

 

이 방법이 잘못된 접근 방식은 아니지만, 최악의 경우에 n+(n-1) + ... + 1 = O(n^2)의 시간이 걸리므로 비효율적이다. (이 경우에도 역시 시간 초과가 떴다)

 

[2nd Try] - 스택

- 잘못된 접근
 1) 인덱스마다 결과값을 담을 딕셔너리 counter를 선언
 2) 스택을 만들어서 T의 원소를 push함.
 3) 이후에 pop하면서 counter 내 해당 값의 자리에 1씩 추가해줌.
 4) 다음 원소(T[i])가 pop한 값보다 크면 3)의 과정을 반복함. 이때, stack이 비어있다면 3)을 반복할 수 없으므로, i를 stack에 push함.
 5) T[i]가 pop한 값보다 작거나 같다면, pop한 값을 다시 스택에 push하고, 현재 인덱스 또한 push해줌.
 6) T의 모든 원소에 대해 다 탐색을 마쳤다면, 스택에 남아있는 원소들의 counter를 모두 0으로 바꿔줌.
 7) 종료

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        """
        스택으로 접근
        """
        counter = {k:0 for k in range(len(T))} 
        # counter dict: 인덱스로 해야됨 (동일한 온도가 있을 수 있으므로)
        print(counter)
        stack = [0]
        print(counter)
        
        for i in range(1,len(T)):
            temp = T[i]
            while True:
                print(stack)
                cur_idx = stack.pop()
                cur_temp= T[cur_idx]
                counter[cur_idx] += 1
                if cur_temp >= temp: # 현재보다 더 따뜻한 날씨를 못만남
                    stack.append(cur_idx) # cur_temp 다시 push
                    stack.append(i) # temp도 뒤이어 push
                    break # while loop 탈출 -> temp 변경
                elif not stack: # 더 따뜻한 날씨 발견 + stack이 비어있을 경우(더 쌓여있는 일자가 없는 경우)
                    stack.append(i)
                    break
                                    
        while stack:
            counter[stack.pop()] = 0
        
        return list(counter.values())
            

위의 접근을 시도해본 결과, 인풋 시퀀스 T가 [73,74,75,71,69,72,76,73] 이라고 했을 때 75에 대한 카운팅을 제대로 하지 못한다는 문제가 있었다. 이는 69를 스택에 push할 때 75가 비교가 아예 되지 않는 구조이기 때문이다. 71과만 비교하고 바로 if cur_temp >= temp에서 걸려버리기 때문에 75가 아예 pop이 되지 않아서 counter에도 추가되지 않는다. 따라서 위의 접근은 현재 온도보다 낮은 미래가 2일 이상 지속될 시 제대로 답을 찾을 수 없다.

- 올바른 접근
 위의 부분에서 문제가 되는 점은 바로 카운팅에 있었다. pop할 때마다 counter를 업데이트시키는 구조가 문제가 되었고, 따라서 카운팅하는 방법을 바꿔본다. 스택이 기온이 아니라 인덱스를 담는다는 점을 살펴보면, 보다 기온이 높은 날을 만나는 데까지 소요되는 기간은 인덱스 차이로 생각해볼 수 있다. 따라서 이를 반영하여 수정한 코드는 아래와 같다.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        """
        스택으로 접근
        """
        counter = {k:0 for k in range(len(T))} 
        # counter dict: 인덱스로 해야됨 (동일한 온도가 있을 수 있으므로)
        stack = [0]
        
        for i in range(1,len(T)):
            temp = T[i]
            while True:
                cur_idx = stack.pop()
                cur_temp= T[cur_idx]
                if cur_temp >= temp: # 현재보다 더 따뜻한 날씨를 못만남 (탐색 실패)
                    stack.append(cur_idx) # cur_temp 다시 push
                    stack.append(i) # temp도 뒤이어 push
                    break # while loop 탈출 -> temp 변경
                else: # 탐색 성공
                    counter[cur_idx] = i-cur_idx # counter 업데이트하는 부분을 수정
                    if not stack: # when stack is empty
                        stack.append(i)
                        break
                                    
        while stack:
            counter[stack.pop()] = 0
        
        return list(counter.values())
            

 다만 위의 코드는 반복문을 종료하는 조건들이 약간 복잡하기 때문에 이러한 부분을 수정할 수 있을 듯하다. 또한 딕셔너리 키값이 리스트의 인덱스와 일치한다는 점에서 딕셔너리가 아닌 리스트로 충분히 counter의 자료구조를 대체할 수 있다.
 보다 간결한 코드는 아래와 같다.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        """
        스택으로 접근
        """
        counter = [0 for i in range(len(T))]
        stack = [0]
        
        for i, cur in enumerate(T):
            # when stack is not empty and current temp is higher than temp of top of stack
            while stack and cur > T[stack[-1]]: # stack의 마지막 요소를 그냥 봄..(pop 없이)
                top = stack.pop()
                counter[top] = i - top
            stack.append(i)
        
        return counter

---

단순 자료구조 공부를 넘어서 문제에 적용해보는 건 여전히 좀 까다로운 듯하다. 문제에 어떤 식으로 적용을 해볼까 하는 부분을 조금 더 연습하는 게 필요할 듯. 그리고 코드를 좀 더 깔끔히 하는 방법도 계속 연구해야할 듯하다.