[코딩 테스트] 2026-03-18 — 단조 스택

오늘의 문제 선정 이유

 

데이터 흐름을 한 번 훑으며 다음 상태 변화를 찾는 문제는 실무와 코딩 테스트 둘 다 자주 나오기 때문입니다.

문제 설명

한 개발팀은 14일 동안의 서버 평균 CPU 온도를 기록했습니다.
각 날짜마다 "이 날짜보다 더 높은 온도가 처음 나타나는 날"까지 몇 일이 걸리는지 구하려고 합니다.

정수 배열 temps가 주어질 때, 각 인덱스 i에 대해 temps[i]보다 큰 값이 처음 등장하는 날짜까지의 일수를 담은 배열을 반환하세요.
만약 끝까지 가도 더 높은 온도가 없다면 0을 넣습니다.

예를 들어, temps[2] = 71이고 temps[5] = 74가 그 뒤에서 처음으로 더 높은 온도라면, 정답 배열의 2번 위치에는 3이 들어갑니다.

입출력 예시

[text]입력: temps = [68, 70, 69, 72, 71, 74, 73]
출력: [1, 2, 1, 2, 1, 0, 0]
설명:
68 다음 더 높은 온도는 70이므로 1일
70 다음 더 높은 온도는 72이므로 2일
69 다음 더 높은 온도는 72이므로 1일
72 다음 더 높은 온도는 74이므로 2일
71 다음 더 높은 온도는 74이므로 1일
74보다 높은 온도는 없음
73보다 높은 온도는 없음

[text]입력: temps = [75, 74, 73, 72]
출력: [0, 0, 0, 0]
설명:
모든 날짜에서 이후에 더 높은 온도가 없으므로 전부 0이다.

[text]입력: temps = [60, 60, 61, 60, 62]
출력: [2, 1, 2, 1, 0]
설명:
같은 온도는 "더 높은 온도"가 아니다.
60(0번)은 61(2번)을 만나므로 2일
60(1번)은 61(2번)을 만나므로 1일
61(2번)은 62(4번)을 만나므로 2일
60(3번)은 62(4번)을 만나므로 1일
62(4번)은 이후 더 높은 온도가 없다.

제약 조건

• 1 <= len(temps) <= 100000

 

• -50 <= temps[i] <= 150

 

• 시간 제한: O(n log n) 이내 권장, O(n) 풀이 가능

 

• 같은 온도가 여러 번 등장할 수 있음

풀이 접근법

핵심 아이디어

이 문제는 각 위치에서 "오른쪽에 있는 첫 번째 더 큰 값"을 찾는 문제입니다.
브루트포스로 각 날짜마다 뒤를 끝까지 확인하면 O(n^2)가 되어 길이가 크면 비효율적입니다. 그래서 아직 답을 못 찾은 날짜들을 스택에 모아두고, 더 높은 온도가 나오면 한 번에 처리하는 단조 스택을 사용합니다.

단계별 풀이 과정

1. 정답 배열 answer를 0으로 초기화합니다.
2. 스택에는 아직 더 높은 온도를 만나지 못한 날짜의 인덱스를 넣습니다.
3. 현재 날짜 i를 보면서, 스택 top의 온도보다 현재 온도가 더 높다면 그 날짜의 정답을 i - prevIndex로 채웁니다.
4. 더 이상 pop할 수 없을 때까지 반복합니다.
5. 현재 인덱스 i를 스택에 넣습니다.
6. 끝까지 처리한 뒤 스택에 남아 있는 날짜들은 더 높은 온도가 없으므로 0 그대로 둡니다.

코드 풀이

Python

 

[python]def days_until_warmer(temps):
    n = len(temps)
    answer = [0] * n
    stack = []  # 더 높은 온도를 아직 못 찾은 날짜의 index 저장

    for i in range(n):
        # 현재 온도가 스택 top의 온도보다 높으면 답을 확정할 수 있다
        while stack and temps[i] > temps[stack[-1]]:
            prev_index = stack.pop()
            answer[prev_index] = i - prev_index

        stack.append(i)

    return answer


# 예시 실행
if __name__ == "__main__":
    print(days_until_warmer([68, 70, 69, 72, 71, 74, 73]))  # [1, 2, 1, 2, 1, 0, 0]
    print(days_until_warmer([75, 74, 73, 72]))              # [0, 0, 0, 0]
    print(days_until_warmer([60, 60, 61, 60, 62]))          # [2, 1, 2, 1, 0]

JavaScript

 

[javascript]function daysUntilWarmer(temps) {
  const n = temps.length;
  const answer = new Array(n).fill(0);
  const stack = []; // 더 높은 온도를 아직 못 찾은 날짜의 index 저장

  for (let i = 0; i < n; i++) {
    // 현재 온도가 스택 top의 온도보다 높으면 답을 확정할 수 있다
    while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      answer[prevIndex] = i - prevIndex;
    }

    stack.push(i);
  }

  return answer;
}

// 예시 실행
console.log(daysUntilWarmer([68, 70, 69, 72, 71, 74, 73])); // [1, 2, 1, 2, 1, 0, 0]
console.log(daysUntilWarmer([75, 74, 73, 72]));             // [0, 0, 0, 0]
console.log(daysUntilWarmer([60, 60, 61, 60, 62]));         // [2, 1, 2, 1, 0]

시간·공간 복잡도

• 시간 복잡도: O(n) — 각 인덱스가 스택에 한 번 들어가고 한 번만 나오기 때문

 

• 공간 복잡도: O(n) — 정답 배열과 스택에 최대 n개가 저장될 수 있기 때문

틀리기 쉬운 포인트

• 같은 온도는 더 높은 온도가 아닙니다. 비교 연산은 >=가 아니라 >여야 합니다.

 

• 스택에 온도값 자체가 아니라 인덱스를 넣어야 날짜 차이 계산이 쉽습니다.

 

• 끝까지 더 높은 온도를 못 만난 날짜는 따로 처리하지 않아도 됩니다. 정답 배열을 처음부터 0으로 채우면 됩니다.

유사 문제 패턴

• 주가가 떨어지기까지 걸리는 시간: 현재 값보다 작은 값이 처음 나오는 시점을 찾는 문제입니다.

 

• 다음 더 큰 수 찾기: 배열에서 각 원소 기준으로 오른쪽 첫 번째 큰 값을 찾는 문제입니다.

 

• 히스토그램 최대 직사각형: 단조 스택으로 구간의 경계를 빠르게 찾는 대표 문제입니다.