Daily Temperatures

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

단조 스택 풀이의 시간 복잡도는 O(n) 이고 추가 공간 복잡도는 O(n) 입니다. 각 날짜는 한 번 푸시되고 최대 한 번 팝되기 때문입니다. 모든 날짜에서 앞으로 탐색하면 시간 복잡도는 O(n²) 이며, 더 따뜻한 날이 없는 10^4일의 경우 비교 횟수는 약 5 × 10^7회입니다.

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

네. 마지막 날부터 거꾸로 답을 채우고, i 일에는 j = i+1 에서 시작합니다. j 일의 기온이 더 높지 않은 동안 j + answer[j] , 즉 j 일의 답이 가리키는 날로 건너뜁니다. answer[j] 가 0이면 i 일의 답도 0입니다. 이 점프는 i 일의 답이 될 수 없는 날들을 건너뜁니다. 시간 복잡도는 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일을 기다립니다. 3일차(70)는 4일차의 같은 온도인 70을 건너뛰고 75를 기다리며 2일을 기다립니다. 75와 68 이후에는 더 따뜻한 날이 없으므로 둘 다 0을 받습니다.

후속 질문

온도는 30부터 100까지 단 71개의 값만 가집니다. 온도를 인덱스로 사용하는 테이블은 어떻게 오른쪽에서 왼쪽으로 한 번만 훑으면서 모든 날짜에 답할 수 있으며, 그 대가는 무엇일까요?

풀이

매일 앞으로 훑으면 작업이 반복되고, 따뜻한 날이 드물면 훑을 때마다 끝까지 진행됩니다. 대신 날짜를 한 번만 살펴보면서 새 날짜가 자신보다 앞선 날짜 중 이기는 날짜에 답하도록 하세요. 아직 답을 기다리는 날짜들은 아래에서 위로 온도가 올라가지 않는 스택에 놓이므로, 모든 답을 한 번의 순회로 구할 수 있습니다.

매일 앞으로 스캔하기

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

핵심 아이디어

날짜 i에 대해 i+1, i+2 등의 날짜를 확인하고, 처음으로 더 따뜻한 날짜 j에서 멈춥니다. 답은 j-i이며, 끝까지 확인해도 찾지 못하면 0입니다. 순서대로 확인하므로 처음 만나는 더 따뜻한 날이 가장 먼저 나타나는 날입니다.

10^4일 모두 기온이 같다면 어떤 확인도 일찍 멈추지 않습니다. 비교 횟수는 약 n²/2 = 5 × 10^7회이고, 1일차는 0일차가 이미 확인한 것과 거의 같은 범위를 다시 확인합니다.

알고리즘

하루마다 항목 하나씩 0으로 채운 answer 배열을 만듭니다.
각 날짜 i에 대해 i+1부터 마지막 날까지 j를 탐색합니다.
temperatures[j] > temperatures[i]인 첫 번째 j에서 j-i를 저장하고 탐색을 중단합니다.
answer 배열을 반환합니다. 탐색 중 아무것도 찾지 못한 날짜에는 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입니다. 그런 다음 오늘을 스택에 넣습니다.

맨 위만 확인하면 됩니다. 기온이 더 낮은 날은 그 위에 있는 더 낮은 날을 모두 꺼낸 뒤에야 스택에 들어오므로, 스택의 기온은 아래에서 위로 갈수록 절대 높아지지 않습니다. 오늘의 기온이 맨 위의 기온보다 높지 않다면 아래에 있는 어떤 날의 기온보다도 높지 않으므로, 꺼내기를 멈춥니다. 첫 번째 예시에서는 5일째(75)가 4일째, 3일째, 2일째를 꺼내며 대기 기간은 각각 1, 2, 3일입니다. 반면 두 번째 70은 첫 번째 70을 꺼내지 않았는데, 같은 기온은 더 높은 기온이 아니기 때문입니다.

각 날은 한 번 스택에 들어가고 최대 한 번 꺼내지므로, 꺼내는 횟수의 합은 최대 n입니다. 따라서 하루가 여러 날을 꺼낼 수 있더라도 시간 복잡도는 O(n)입니다.

알고리즘

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

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

함정과 경계 사례

>=에서 꺼내고 >에서는 꺼내지 않는 경우. 첫 번째 예시에서 3일째는 두 번째 70을 기다리느라 75를 기다리는 대신 1일을 기다립니다.
인덱스 대신 온도를 넣는 경우. 그러면 거리를 계산하거나 답의 어느 항목을 채워야 하는지 알 수 없습니다.
while이 필요한 곳에 if를 사용하는 경우. 따뜻한 하루 하나가 여러 대기일의 답이 될 수 있습니다. 첫 번째 예시에서 75는 세 날짜의 답이 됩니다.
스택에 남아 있는 날짜의 답을 설정하지 않는 경우. 답은 0입니다. C에서는 malloc 메모리에 쓰레기 값이 들어 있으므로 calloc으로 답을 할당하세요.
앞으로 탐색할 때 첫 번째로 더 따뜻한 날을 지나 계속 탐색하는 경우. break가 없으면 대신 마지막으로 더 따뜻한 날을 기록합니다.

자주 묻는 질문3

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

단조 스택 풀이의 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(n)입니다. 각 날짜는 한 번 푸시되고 최대 한 번 팝되기 때문입니다. 모든 날짜에서 앞으로 탐색하면 시간 복잡도는 O(n²)이며, 더 따뜻한 날이 없는 10^4일의 경우 비교 횟수는 약 5 × 10^7회입니다.

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

네. 마지막 날부터 거꾸로 답을 채우고, i일에는 j = i+1에서 시작합니다. j일의 기온이 더 높지 않은 동안 j + answer[j], 즉 j일의 답이 가리키는 날로 건너뜁니다. answer[j]가 0이면 i일의 답도 0입니다. 이 점프는 i일의 답이 될 수 없는 날들을 건너뜁니다. 시간 복잡도는 O(n)이고, 추가 메모리는 사용하지 않습니다.

일일 기온은 다음으로 큰 원소와 어떤 관련이 있나요?

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

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

테스트 #1

테스트 #2

테스트 #3

인자

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

예상 출력

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