[LeetCode-739] 스택엔 인덱스를 쌓았는데, 비교는 값이랑 했다

스택·큐 개념과 자주 쓰는 메서드는 카테고리 총정리 글에서 다룬다. LC496에 이어지는 몬로토닉 스택 두 번째 문제.

• 문제 링크: https://leetcode.com/problems/daily-temperatures/
• 파일 경로: src/main/java/coding_test/스택_큐/LC0739_DailyTemperatures.java
• 난이도: Medium

문제 설명

일별 기온 배열 temperatures가 주어진다. answer[i]가 “i번째 날 이후로 더 따뜻한 날이 오기까지 며칠을 기다려야 하는지”가 되도록 배열을 반환한다. 그런 날이 없으면 0.

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

시행착오

1차 — 값으로 관리한 HashMap 방식이 완전히 틀어짐. 처음엔 496의 방식(값 → 정답을 매핑하는 HashMap)을 그대로 가져오려 했는데, 이 문제는 같은 온도가 여러 번 나올 수 있어서(Edge: [50,50,50]) 값 하나로는 “몇 번째 날인지”를 구분할 수가 없었다. 결과가 완전히 이상하게 나와서([9,9,9] 같은) 접근 자체를 다시 짰다.

2차 — 이중 반복문 브루트포스는 로직은 맞는데 시간 초과. for (i) { for (j=i) { ... } }로 “그 이후 날짜들을 하나씩 확인”하는 방식으로 다시 짜서 로직 자체(47/48 테스트)는 맞았는데, 배열 길이가 큰 마지막 테스트에서 Time Limit Exceeded가 났다. O(n²)라서 temperatures.length가 10^5일 때 감당이 안 됐다.

3차 — 몬로토닉 스택인데, 스택에 뭘 담았는지를 착각함. “아직 따뜻한 날을 못 찾은 날짜들의 인덱스”를 스택에 쌓고, 더 따뜻한 날을 만나면 꺼내서 날짜 차이를 계산하는 구조로 바꿨다. 그런데

while (!stack.isEmpty() && stack.peek() < temperatures[i]) {

이렇게 짰다 — 스택엔 인덱스를 넣어놓고(stack.push(i)), 비교는 stack.peek()(인덱스)를 마치 온도인 것처럼 temperatures[i](온도)랑 직접 비교했다. 타입은 둘 다 int라 컴파일 에러는 안 나지만, 의미상 “3번째 날”이라는 인덱스와 “76도”라는 온도를 비교하는 꼴이라 완전히 틀린 값이 나왔다. temperatures[stack.peek()]로 그 인덱스가 가리키는 실제 온도를 가져와서 비교하도록 고쳤다.

최종 코드

public int[] dailyTemperatures(int[] temperatures) {
    int[] ans = new int[temperatures.length];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int num = stack.pop();
            ans[num] = i - num;
        }
        stack.push(i);
    }

    return ans;
}

오늘 배운 내용

스택에 “무엇을 담을지”를 정했으면, 그 이후의 모든 비교/연산이 그 담긴 것의 타입을 기준으로 이루어져야 한다. 인덱스를 담기로 해놓고 값처럼 비교하면, 컴파일러는 잡아주지 못하는(둘 다 int라서) 의미론적 버그가 생긴다. 그리고 496과 739는 겉보기엔 비슷한 몬로토닉 스택 문제지만, “값 하나로 구분이 되는가”(496은 원소가 서로 다름 보장, 739는 중복 가능)에 따라 스택/맵에 값을 담을지 인덱스를 담을지가 완전히 달라진다는 것도 이번에 제대로 배웠다.

오답노트

• 틀렸던 패턴 1: 496처럼 HashMap<온도, 정답>으로 접근 — 중복 온도가 있으면 값이 서로 덮어써짐.
• 왜 틀렸나: “원소가 유일하다”는 496의 전제를 739에도 그대로 적용했다.
• 틀렸던 패턴 2: 이중 반복문 브루트포스 — 로직은 맞지만 O(n²)라 TLE.
• 왜 틀렸나: 정답을 맞히는 것과 시간 제한 안에 맞히는 것은 다른 기준이라는 걸 뒤늦게 확인했다.
• 틀렸던 패턴 3: 스택엔 인덱스를 넣고, 비교는 stack.peek()을 값처럼 사용.
• 왜 틀렸나: 스택에 “무엇”을 담기로 했는지(인덱스)와 그 담긴 것을 “어떻게” 써야 하는지(그 인덱스로 배열을 다시 조회)를 연결하지 못했다.
• 다음에 떠올릴 시점: 스택/큐에 인덱스를 담을 때는, 이후 코드에서 stack.peek()이 나올 때마다 “이게 인덱스니까 실제 값을 보려면 배열로 한 번 더 조회해야 한다”는 걸 매번 의식적으로 확인한다.

AI라면 어떻게 풀었을까

지금 코드가 이미 몬로토닉 스택의 정석 풀이라 별다른 최적화는 필요 없다. 대신 496과 739를 나란히 놓고 보면, “원소가 유일한가” 하나로 두 문제의 자료구조 선택이 갈린다는 걸 일반화해볼 수 있다.

// 496: 값이 유일 -> 값 자체를 키로 쓴 Map으로 충분
Map<Integer, Integer> nextGreater = new HashMap<>();

// 739: 값이 중복 가능 -> 인덱스를 담아야 날짜(위치)를 구분 가능
Deque<Integer> stack = new ArrayDeque<>(); // 인덱스 저장

몬로토닉 스택 문제를 마주치면 “정답을 인덱스로 구분해야 하는가, 값만으로 충분한가”를 가장 먼저 판단하는 게 두 문제를 겪고 나서 생긴 새로운 체크리스트다.