Daily Temperatures

Q: Daily Temperatures의 시간 복잡도는 무엇인가요?

단조 스택 솔루션은 O(n) 시간과 O(n) 의 추가 공간을 사용합니다. 각 날짜는 한 번 푸시되고 최대 한 번 팝되므로, 전체 순회에서 내부 루프는 최대 n 번 실행됩니다. 각 날짜부터 앞으로 훑으면 O(n²) 시간이 걸리며, 더 따뜻한 날이 없는 경우 10^4일에 대해 약 5 × 10^7번 비교합니다.

Q: 스택은 왜 온도 대신 인덱스를 저장하나요?

하루에 대한 답은 거리인 today - day 이므로, 그날의 위치가 필요합니다. 인덱스는 해당 날짜가 스택에서 꺼내졌을 때 답 배열의 어느 항목을 채워야 하는지도 알려 줍니다. 온도는 temperatures[day] 로 한 번 조회하면 되므로, 온도까지 저장해도 얻는 것이 없습니다.

Q: 일일 기온 문제를 스택 없이 풀 수 있을까요?

네. 마지막 날부터 첫날까지 거꾸로 살펴보고, i 일에는 j = i+1 에서 시작합니다. j 일이 더 따뜻하지 않은 동안 j 에 대한 답을 더한 날인 j + answer[j] 로 건너뜁니다. answer[j] 가 0이면 더 따뜻한 날이 없으므로 i 일의 값도 0이 됩니다. 이렇게 건너뛰면 답이 될 수 없는 날은 모두 제외되고, 각 날은 최대 한 번만 건너뛰어지므로 답 배열 외에는 메모리를 사용하지 않으면서 시간 복잡도는 O(n) 으로 유지됩니다.

보통단조 스택

+10

연속된 날짜 각각의 온도가 주어집니다. temperatures[i]는 i일의 온도입니다. 각 날짜에 대해 그날 이후로 더 따뜻한 날이 올 때까지 며칠을 기다려야 하는지 세세요. 나중에 더 따뜻한 날이 오지 않는다면 해당 날짜의 대기 일수는 0입니다.

길이가 같은 배열을 반환하세요. 배열의 항목 i는 i일의 대기 일수입니다.

함수

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: 각 날짜의 기온을 순서대로
반환값integer-array: 각 날짜에 대해 더 따뜻한 날이 올 때까지 남은 일수 또는 그런 날이 없으면 0

제약 조건

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
더 따뜻하다는 것은 엄밀히 말해 기온이 더 높다는 뜻입니다. 나중 날짜의 기온이 같다면 해당하지 않습니다.

예제

입력: temperatures = [71, 69, 72, 70, 70, 75, 68]
출력: [2, 1, 3, 2, 1, 0, 0]
설명: 0일째는 71이고 첫 번째로 더 따뜻한 날은 72인 2일째이므로 2일을 기다립니다. 3일째와 4일째는 모두 70입니다. 두 번째 70은 더 따뜻하지 않으므로 3일째는 75인 5일째까지 기다리며, 이는 2일입니다. 75나 68 이후에는 더 따뜻한 날이 없으므로 둘 다 0입니다.

제출 시 숨은 테스트 +13개

후속 질문

온도는 30부터 100까지 총 71개의 값만 가집니다. 온도를 인덱스로 사용하는 테이블은 오른쪽에서 왼쪽으로 한 번만 훑어서 어떻게 모든 날짜에 답을 구할 수 있을까요? 그리고 그 과정의 비용은 얼마일까요?

풀이

하루의 답을 구할 때는 앞에서부터 스캔하면 되지만, 모든 날을 대상으로 스캔하면 같은 작업이 반복되고 따뜻한 날이 드물면 스캔할 때마다 배열의 끝까지 가게 됩니다. 해결 방법은 각 날이 이후의 날에 대해 묻는 대신 이전 날들에 답하도록 하는 것입니다. 아직 답을 기다리는 인덱스들을 담고 온도순으로 정렬된 상태를 유지하는 스택을 사용하면 한 번의 순회만으로 모든 답을 구할 수 있습니다.

매일 앞으로 스캔합니다

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

문제에서 요구하는 대로 하세요. i일에는 i+1일, 그다음 i+2일 등을 살펴보고, 온도가 엄격히 더 높은 첫날에서 멈춥니다. 거리 j-i가 답입니다. 그런 날을 찾지 못한 채 끝에 도달하면 답은 0으로 유지됩니다.

나중의 날들을 순서대로 살펴보므로 처음 만나는 더 따뜻한 날이 실제로 존재하는 첫 번째 더 따뜻한 날이기 때문에 이 방법은 올바릅니다. 바로 그 지점에서 멈추는 것도 중요합니다. 계속 살펴보는 방식은 대신 마지막으로 더 따뜻한 날을 기록하게 됩니다.

더 따뜻한 날이 멀리 있거나 아예 없으면 느립니다. 10^4일의 온도가 모두 같다면 어떤 탐색도 일찍 멈추지 않습니다. 0일째에는 9,999일을 확인하고, 1일째에는 9,998일을 확인하므로, 총 비교 횟수는 약 n²/2 = 5 × 10^7입니다. 탐색 범위도 서로 겹칩니다. 1일째의 탐색은 0일째에 이미 탐색한 구간을 거의 그대로 다시 훑으면서도 아무것도 새로 알아내지 못합니다.

알고리즘

일별로 하나씩 항목을 두어 0으로 채운 답 배열을 만듭니다.
각 날짜 i에 대해, j를 i+1부터 마지막 날까지 살펴봅니다.
temperatures[j] > temperatures[i]인 첫 번째 j에서 j-i를 저장하고 탐색을 멈춥니다.
답 배열을 반환합니다. 탐색에서 아무것도 찾지 못한 날은 0을 유지합니다.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

기다리는 날의 단조 스택

핵심 아이디어

질문을 뒤집어 보세요. 매일 그다음에 무엇이 오는지 묻는 대신, 날짜를 한 번 훑으면서 새로 온 날이 자신보다 앞선 날들 중 더 따뜻한 날을 기다리던 날에 답하게 하세요. 아직 답을 얻지 못한 날들은 인덱스로 스택에 보관합니다. 오늘이 오면 오늘보다 추운 대기 중인 날들은 모두 처음으로 더 따뜻한 날을 찾은 것입니다. 바로 오늘입니다. 각 날짜를 스택에서 꺼내고 답으로 today - day를 적으세요. 그런 다음 오늘을 스택에 넣습니다. 이제 오늘도 자신보다 더 따뜻한 날을 기다립니다.

[71, 69, 72, 70, 70, 75, 68]을 차례로 살펴보세요. 0일째(71)를 스택에 넣습니다. 1일째(69)는 71보다 따뜻하지 않으므로 맨 위에 넣습니다. 스택에는 [0, 1]일째가 들어 있습니다. 2일째(72)는 1일째(대기 1일)를 꺼낸 다음 0일째(대기 2일)를 꺼내고, 스택에 넣습니다. 3일째와 4일째(70과 70)를 넣습니다. 두 번째 70은 첫 번째 70을 꺼내지 않습니다. 같은 온도는 더 따뜻한 것이 아니기 때문입니다. 5일째(75)는 4일째(대기 1일), 3일째(대기 2일), 2일째(대기 3일)를 꺼냅니다. 6일째(68)를 넣습니다. 마지막까지 5일째와 6일째는 여전히 기다리는 중이므로 답은 0으로 둡니다. 답은 [2, 1, 3, 2, 1, 0, 0]입니다.

맨 위만 확인하면 되는 이유는 스택의 온도가 아래에서 위로 갈수록 높아지지 않기 때문입니다. 어떤 날을 스택에 넣는 것은 그 위에 있던 더 추운 날을 모두 꺼낸 뒤이므로, 그 아래에 있는 모든 날은 그 날만큼 또는 그보다 더 따뜻합니다. 오늘이 맨 위의 날보다 더 따뜻하지 않다면, 그 아래의 어느 날보다도 더 따뜻하지 않으므로 꺼내기를 멈춰도 됩니다. 어떤 날은 처음으로 더 따뜻한 날이 나타나는 순간 스택에서 빠지므로, 기록하는 대기 기간은 가장 따뜻한 날까지가 아니라 처음으로 더 따뜻한 날까지입니다.

답은 거리이고 답의 어느 항목을 채워야 하는지 알아야 하므로, 스택에는 온도가 아니라 인덱스를 넣습니다. temperatures[day]를 사용해 온도를 다시 읽으세요. 각 날은 한 번 스택에 들어가고 최대 한 번 꺼내지므로, 전체를 훑는 동안 발생하는 꺼내기의 총횟수는 최대 n이며, 하루에 여러 날을 꺼낼 수 있더라도 전체 시간은 O(n)입니다.

알고리즘

0으로 채워진 answer 배열과 빈 인덱스 스택을 만듭니다.
각 날짜 today에 대해, 스택 맨 위의 날짜가 오늘보다 더 추울 동안 그 날짜를 꺼내고 해당 날짜의 정답을 today에서 그 날짜의 인덱스를 뺀 값으로 설정합니다.
today를 스택에 넣습니다.
반복문이 끝난 후에도 스택에 남아 있는 날짜에는 더 따뜻한 날이 없으므로 0을 유지합니다. answer 배열을 반환합니다.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

함정과 경계 사례

스택 루프는 몇 줄이면 되지만, 버그는 비교 연산과 스택에 무엇을 넣는지에 숨어 있습니다.

> 대신 >=일 때 pop하기. 온도가 같은 날은 더 따뜻한 날이 아닙니다. [71, 69, 72, 70, 70, 75, 68]에서 3일째는 두 번째 70이 아니라 75가 올 때까지 2일을 기다립니다.
인덱스 대신 온도를 push하기. 정답은 날짜 간 거리이므로, 이를 계산하고 값을 채울 항목을 알기 위해 인덱스가 필요합니다.
while이 필요한 곳에 if를 사용하기. 따뜻한 하루가 기다리던 여러 날짜의 답이 될 수 있습니다. 첫 번째 예시에서 75는 세 날짜의 답입니다.
더 따뜻한 온도나 더 따뜻한 날의 인덱스를 반환하기. 출력값은 기다리는 날짜 수인 j-i입니다.
스택에 남아 있는 날짜의 값을 설정하지 않기. 이 날짜들의 답은 0입니다. C에서는 calloc으로 답 배열을 할당하거나 직접 값을 채우세요. malloc으로 할당한 메모리에는 쓰레기값이 들어 있습니다.
앞으로 진행하는 탐색이 첫 번째로 더 따뜻한 날을 지나치게 하기. break가 없으면 첫 번째 날이 아니라 마지막으로 더 따뜻한 날을 기록합니다.

자주 묻는 질문4

Daily Temperatures의 시간 복잡도는 무엇인가요?

단조 스택 솔루션은 O(n) 시간과 O(n)의 추가 공간을 사용합니다. 각 날짜는 한 번 푸시되고 최대 한 번 팝되므로, 전체 순회에서 내부 루프는 최대 n번 실행됩니다. 각 날짜부터 앞으로 훑으면 O(n²) 시간이 걸리며, 더 따뜻한 날이 없는 경우 10^4일에 대해 약 5 × 10^7번 비교합니다.

스택은 왜 온도 대신 인덱스를 저장하나요?

하루에 대한 답은 거리인 today - day이므로, 그날의 위치가 필요합니다. 인덱스는 해당 날짜가 스택에서 꺼내졌을 때 답 배열의 어느 항목을 채워야 하는지도 알려 줍니다. 온도는 temperatures[day]로 한 번 조회하면 되므로, 온도까지 저장해도 얻는 것이 없습니다.

일일 기온 문제를 스택 없이 풀 수 있을까요?

네. 마지막 날부터 첫날까지 거꾸로 살펴보고, i일에는 j = i+1에서 시작합니다. j일이 더 따뜻하지 않은 동안 j에 대한 답을 더한 날인 j + answer[j]로 건너뜁니다. answer[j]가 0이면 더 따뜻한 날이 없으므로 i일의 값도 0이 됩니다. 이렇게 건너뛰면 답이 될 수 없는 날은 모두 제외되고, 각 날은 최대 한 번만 건너뛰어지므로 답 배열 외에는 메모리를 사용하지 않으면서 시간 복잡도는 O(n)으로 유지됩니다.

Daily Temperatures는 Next Greater Element와 어떤 관련이 있나요?

모든 위치에서 묻는 질문은 같습니다. 오른쪽에 있는 다음으로 큰 값을 찾는 것입니다. Next Greater Element는 그 값을 반환하고, Daily Temperatures는 그 값이 얼마나 떨어져 있는지 반환하므로 스택에는 인덱스가 들어 있습니다. 더 작은 값에서 꺼내도록 바꾼 동일한 단조 스택은 다음으로 작은 요소를 찾는 질문에도 답할 수 있습니다.

Python

def dailyTemperatures(temperatures):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

temperatures = [71, 69, 72, 70, 70, 75, 68]

기대값

[2, 1, 3, 2, 1, 0, 0]