[자료구조/스택] 일일 온도

문제

• 매일 화씨 온도 리스트 temperature를 입력받을 때, 더 따뜻한 날씨을 위해서는 몇일을 기다려야 하는지 출력
• 더 따뜻한 날씨가 없다면 0으로 표기
• 원본 url : https://leetcode.com/problems/daily-temperatures/

---

예시

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

---

 

문제 풀이 1

• 특별한 자료구조 형태를 적용하지 않고, 단순히 Brute Force 방식으로 풀이
• O(n) 속도로 예상됨. 기본적인 for문과 if문으로 구성

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        result=[]
        for i, t in enumerate(temperatures):
            # 다음 따뜻한 날을 체크하기 위한 변수
            day=0

            # 전체 온도의 개수에서 2개를 뺀 이유는 리스트의 index를 사용하는데
            # index에서 +1 하기 때문에 마지막 index 값에서 1을 더하면 out of range error 발생 
            length=len(temperatures)-2

            # 맨 마지막 값인지 아닌지 체크
            if length >= i:
                # 다음 온도가 현재 온도 보다 높은지 체크하고 만약 낮거나 같다면 day와 i가 +1 증가하여
                # 그 다음 온도를 체크하면서 day값을 측정
                while t >= temperatures[i+1] and i < length:
                    day += 1
                    i += 1

                # 특별한 예외 상황이 있는데
                # 만약 끝까지 확인했는데 더 높은 온도가 없으면 0으로 입력해야 함
                # 이 부분이 없으면 맨 끝까지 확인하면서 증가한 day가 입력될 것으로 예상
                if i==length and t >= temperatures[i+1]:
                    result.append(0)
                else:
                    result.append(day+1)

            # 맨 마지막 값이라면 무조건 0으로 입력
            else:
                result.append(0)

        return result

 

문제 풀이 2

• 현재 index를 stack 자료구로로 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 stack에 쌓아둔 index 지점의 온도 차이 비교
• 만약 더 높다면, stack의 값을 꺼내 현재 index와 비교하여 그 차이를 정답으로 입력한다.
• 즉, 현재 온도가 이전 온도들과 비교할 때 stack에 쌓여 있는 index를 활용할 것이고, 이 index의 값이 현재 온도보다 작다면 해당 index는 추출되고 그 차이가 정답으로 옮겨져서 결국, stack에는 해당 index가 안 쌓여 있을 것이다.
• 속도 : 31ms

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        # 정답 리스트 세팅 (0으로 세팅해두면, 알아서 아래 로직이 거치지 않는 곳은 0으로 세팅 됨)
        answer=[0] * len(temperatures)

        # 위 온도 값의 index를 담을 자료 구조
        stack=[]

        for i, cur in enumerate(temperatures):
            # step1. stack 값이 있는지 확인
            # step2. 현재 온도가 stack의 쌓여 있는 index의 값보다 크다면
            while stack and cur > temperatures[stack[-1]]:
                # stack에서 해당 index 추출
                last = stack.pop()
                # 해당 index 위치에 정답 입력
                # 현재 i 와 차이값으로 세팅
                answer[last]=i-last

            # 현재 온도의 index가 추가 돼야 추후 온도들과 비교 가능
            stack.append(i)

        return answer