[LeetCode-962] 처음 보는 '투 패스 스택' 기법 - 값이 아니라 거리가 기준

스택·큐 개념과 자주 쓰는 메서드는 카테고리 총정리 글에서 다룬다. LC739 3차 재작성에서 힌트 없이 통과한 뒤 바로 이어진 새 Medium 변형.

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

문제 설명

정수 배열 nums에서 i < j이고 nums[i] <= nums[j]를 만족하는 쌍 (i, j)를 “램프”라 하고, 그 너비는 j - i다. 최대 너비를 구하라.

Input: nums = [6,0,8,2,1,5]
Output: 4  // (i,j)=(1,5): nums[1]=0, nums[5]=5

시행착오

1차 시도 — “조건을 만족하는 j의 개수”를 세고 있었다. 이중 반복문으로 각 i마다 nums[j] >= nums[i]인 j가 몇 개인지 counter로 셌는데, 이건 “너비(거리)”가 아니라 “개수”였다. 예제 2([9,8,1,0,1,9,4,0,4,1])에서 기대값 7인데 6이 나와서 발견했다 — i=2에서 조건을 만족하는 j가 5개 있다고 해서, 그중 가장 먼 j까지의 거리가 5라는 뜻은 아니었다.

2차 시도 — 이중 반복문으로 직접 j-i의 최댓값을 구하도록 고쳐서 정답은 맞았지만, O(n²)라 시간 초과. nums.length가 5*10^4까지 가능해서 이중 반복문 자체가 너무 느렸다.

3차 시도에서 “가장 큰 값을 가진 j”를 찾으려 했는데, 이것도 틀린 방향이었다. i 뒤에서 값이 가장 큰 j를 찾아 너비를 구하려 했는데, [6,0,8,2,1,5]의 i=1(값 0)에서 가장 큰 값은 8(인덱스 2, 너비 1)이지만, 실제 정답은 5(인덱스 5, 너비 4)였다. 조건을 만족하는 값들 중 “가장 큰 값”이 아니라 “가장 멀리 있는(인덱스가 큰) 것”을 찾아야 한다는 걸 다시 확인했다.

결국 처음 보는 기법(투 패스 스택)을 배워서 적용했다. 지금까지 풀었던 몬로토닉 스택 문제(496/739/503/901)는 전부 한 번의 순회로 바로 답을 구하는 단일 패스였는데, 이 문제는:

1. 왼쪽→오른쪽으로 한 번 훑으면서, “왼쪽 끝(i) 후보”만 스택에 쌓는다 — 값이 계속 감소할 때만 push.
2. 오른쪽→왼쪽으로 한 번 더 훑으면서, 스택에 쌓인 후보들과 매칭한다.

이 두 단계를 수도코드로 받아서 그대로 Java로 옮겼다.

최종 코드

public int maxWidthRamp(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < nums.length; i++) {
        if (stack.isEmpty() || nums[i] < nums[stack.peek()]) {
            stack.push(i);
        }
    }

    int ans = 0;
    for (int j = nums.length - 1; j >= 0; j--) {
        while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
            int val = stack.pop();
            ans = Math.max(ans, j - val);
        }
    }

    return ans;
}

오늘 배운 내용

“조건을 만족하는 것 중 최댓값(값 기준)”과 “조건을 만족하는 것 중 가장 먼 것(거리 기준)”은 전혀 다른 질문이다. 값이 크다고 거리가 먼 것도 아니고, 그 반대도 아니다. 이번 문제의 “너비”는 순전히 인덱스 차이이므로, 값의 크기가 아니라 “오른쪽에서부터 순회하면서 가장 먼저 매칭되는 것”을 찾는 방식(투 패스)으로 접근해야 했다. 그리고 지금까지 익힌 몬로토닉 스택이 전부 “단일 패스”였다는 것도, 이 문제를 통해 “왼쪽에서 후보를 추리고 오른쪽에서 매칭하는” 투 패스 패턴도 있다는 걸 새로 배웠다.

오답노트

• 틀렸던 패턴 1: 조건을 만족하는 j의 개수를 셈 — 너비(거리)와는 다른 값.
• 틀렸던 패턴 2: 이중 반복문으로 직접 j-i를 구해 정답은 맞혔지만 O(n²)로 시간 초과.
• 틀렸던 패턴 3: 조건을 만족하는 값들 중 가장 큰 값을 찾으려 함 — 값의 크기와 인덱스 거리는 무관하다는 걸 놓침.
• 다음에 떠올릴 시점: “최대/최소 거리(너비)”를 구하는 문제에서 “값이 가장 큰/작은 것”으로 접근하려는 유혹이 들면, 그게 정말 “거리”와 같은 기준인지 예제로 먼저 확인한다. 그리고 단일 패스로 안 풀리는 몬로토닉 스택 문제를 만나면, “왼쪽에서 후보를 추리고 오른쪽에서 매칭하는” 투 패스 구조를 떠올린다.

AI라면 어떻게 풀었을까

스택에 인덱스만 담으면 값을 확인할 때마다 nums[stack.peek()]로 배열을 다시 조회해야 한다. 인덱스와 값을 한 쌍으로 묶어서 담으면 그 조회가 없어진다.

public int maxWidthRamp(int[] nums) {
    Deque<int[]> stack = new ArrayDeque<>(); // {index, value}
    for (int i = 0; i < nums.length; i++) {
        if (stack.isEmpty() || nums[i] < stack.peek()[1]) {
            stack.push(new int[] { i, nums[i] });
        }
    }

    int ans = 0;
    for (int j = nums.length - 1; j >= 0; j--) {
        while (!stack.isEmpty() && stack.peek()[1] <= nums[j]) {
            int[] candidate = stack.pop();
            ans = Math.max(ans, j - candidate[0]);
        }
    }
    return ans;
}

구조와 두 패스 전략은 똑같고, 스택이 “인덱스”만 들고 다니는 대신 “그 인덱스의 값”까지 같이 들고 다닌다는 점만 다르다. 이렇게 하면 비교할 때마다 원본 배열(nums)을 다시 들여다볼 필요가 없어서, 스택만 보고도 그 안의 내용을 알 수 있다 — 739/503/901에서 “인덱스만 저장하고 값은 배열에서 다시 찾는” 방식을 써왔는데, 그 반대로 “필요한 값을 스택에 미리 같이 넣어두는” 선택도 가능하다는 걸 보여주는 변형이다.

감독관 메모

처음 보는 기법이라 수도코드를 받고 그대로 번역하는 식으로 풀었다. 이건 739 계열에서 반복됐던 “체크리스트 자동화 안 됨”과는 다른 종류의 어려움이다 — 아예 처음 배우는 패턴이라 당연히 막막할 수 있는 지점이고, 수도코드를 Java로 정확히 옮기는 것 자체는 잘 해냈다. 이 기법(투 패스 스택)을 다른 문제에서도 알아보고 적용할 수 있는지가 다음 확인 포인트다.