[LeetCode] 739번 Daily Temperatures 문제 풀이 (파이썬) 그리고 enumerate에 대한 고찰

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

Daily Temperatures - LeetCode

문제 자체는 그렇게 어렵지는 않다. 인덱스 값들을 저장해둘 필요가 있다는 점만 파악하면 스택으로 쉽게 구현이 가능하다. 그런데 enumerate로 값과 함께 저장하려고 하니 시간 제한에 걸린 반면, 인덱스만 저장했을 때는 잘 풀렸는데 도대체 이유가 뭔지 아직도 잘 모르겠다. enumerate로 저장하고 불러올 때 더 시간 복잡도가 높은 것일까? 아시는 분이 계시다면 댓글 부탁드립니다🙇‍♀️

 

우선 타임 리밋으로 실패한 코드부터

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    
        stack = [] # 스택에는 (i, temp)를 저장하려고 했다
        # result를 빈 리스트로 초기화할 경우 팝했을 시 인덱스가 뒤엉키기 때문에 [0] * len(temperatures)로 초기화하였다.
        # 그리고 문제 조건 중에 디폴트로 리턴해야 하는 값이 0이었기 때문이기도 하다.
        result = [0] * len(temperatures)
        
        # temperatures 요소 각각의 인덱스값과 온도에 대하여
        for i, temp in enumerate(temperatures):
            # 스택이 비어있지 않고 스택의 마지막 요소의 온도값이 temp보다 낮다면, 즉 현재의 온도가 스택 마지막 날의 온도보다 높다면
            while stack and stack[-1][1] < temp:
                
                # 스택에서 해당 enumerate를 팝 해준 후, enumerate의 첫 번째 요소인 인덱스를 꺼낸다
                pop = stack.pop()
                idx = pop[0]
                
                # 팝한 인덱스를 현재 날짜의 인덱스에서 빼준 후 result에 덧붙인다.
                result[idx] = i - idx
                
            # 스택에 현재의 인덱스값과 온도 enumerate를 푸쉬해준다.
            stack.append((i, temp))
            
        return result

나름대로 잘 짰다고 생각한 코드지만 시간 제한에 걸렸다. 지난 주에 풀어서 통과했었던 문제라, 도대체 무엇이 문제일까 싶어서 살짝 지난 주의 코드를 다시 들여다봤다. 변수명 등의 의미 없는 차이를 제외하고는, 지난 주 풀이에서는 스택에 enumerate를 통으로 붙이지 않고 인덱스값만 붙였다는 게 유일한 차이였다.

그래서 거기서 힌트를 얻어 재도전했더니, 다른 모든 제출들 대비 97%나 빠른 속도로 풀이에 성공했다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [] # 바뀐 점이라곤 이 스택에 enumerate가 아닌 인덱스만 넣는다는 점
        result = [0] * len(temperatures)
        
        # 현재 날짜의 인덱스 역시 필요하기에 여기서는 enumerate로 반복문을 형성한다.
        for i, temp in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < temp:
                pop = stack.pop() # 팝한 값 자체가 인덱스
                result[pop] = i - pop
            stack.append(i) # 스택에는 enumerate 전체가 아닌 i만을 푸쉬해준다.
            
        return result

enum을 통으로 푸쉬한 게 그렇게 비효율적인 걸까? 이해가 가지 않는다...