[LeetCode] 845. Longest Mountain in Array

배열에서 가장 긴 "산"의 길이를 구하는 문제다. 산은 엄격히 올라갔다가 엄격히 내려오는 구간이고, 길이가 3 이상이어야 한다.

입력: [2,1,4,7,3,2,5]
출력: 5   // [1,4,7,3,2]

첫 시도: 시작점에서 끝점까지 훑기

처음엔 시작점 start 를 잡고 end 를 오른쪽으로 늘리면서 오르막인지 내리막인지 플래그로 추적했다. 내리막이 끝나고 다시 오르는 순간을 "산이 끝났다"로 보고 길이를 기록했다.

for (let start = 0; start < n; start++) {
  let isUphill = true;
  for (let end = start + 1; end < n; end++) {
    if (arr[start] === arr[end]) break;
    const len = end - start + 1;
    if (isUphill) {
      if (arr[start] > arr[end]) isUphill = false;
    } else if (arr[start] < arr[end]) {
      largest = Math.max(largest, len);
      break;
    }
  }
}

두 가지가 틀렸다.

1. 인접 원소가 아니라 arr[start] 와 arr[end] 를 비교한다. 오르막·내리막은 바로 옆 원소와의 관계인데, 시작점 기준 높낮이를 보고 있었다.
2. 길이를 기록하는 시점이 "다시 오르막이 시작될 때"뿐이다. 산이 배열 끝에서 끝나면 아무도 길이를 적지 않는다. [1,2,3,2,1] 처럼 배열 전체가 산이면 0 이 나온다.

2번을 보고 "배열 끝 케이스를 따로 처리해야 하나" 고민했는데, 그건 증상을 막는 거였다.

관점 전환: 시작점이 아니라 봉우리를 잡는다

산은 봉우리 하나로 결정된다. 봉우리에서 왼쪽으로 "더 못 올라갈 때까지", 오른쪽으로 "더 못 내려갈 때까지" 걸으면 그게 산의 양 끝이다.

이렇게 바꾸면 배열 끝 케이스가 사라진다. 산의 끝은 "더 못 내려가는 곳"이고, 그게 배열 끝이든 평지든 다음 오르막이든 같은 조건으로 멈춘다.

function longestMountain(arr: number[]): number {
  let largest = 0;

  for (let peak = 1; peak < arr.length - 1; peak++) {
    if (!(arr[peak - 1] < arr[peak] && arr[peak] > arr[peak + 1])) continue;

    let left = peak;
    while (0 < left && arr[left - 1] < arr[left]) left--;

    let right = peak;
    while (arr[right] > arr[right + 1] && right < arr.length - 1) right++;

    const len = right - left + 1;
    largest = Math.max(largest, len);
  }

  return largest;
}

코드 읽기

continue 가드

if (!(arr[peak - 1] < arr[peak] && arr[peak] > arr[peak + 1])) continue;

"여기가 꼭대기일 때만 양쪽으로 내려가라"는 뜻이다. 왼쪽이 더 낮고 오른쪽이 더 낮아야 봉우리다. 이 가드가 길이 3 미만을 자연스럽게 걸러 준다. 봉우리가 있으면 양옆이 최소 하나씩 있으니 길이는 항상 3 이상이고, [1,2,3] 처럼 오르막만 있으면 봉우리가 없어서 0 이 된다.

양쪽으로 걷기

while (0 < left && arr[left - 1] < arr[left]) left--;
while (arr[right] > arr[right + 1] && right < arr.length - 1) right++;

왼쪽은 "왼쪽 원소가 더 작으면" 계속, 오른쪽은 "오른쪽 원소가 더 작으면" 계속. 같은 값이 나오면 부등식이 깨져서 멈춘다. 엄격한 증가·감소 조건이 비교 연산자 하나로 끝난다.

복잡도

• 시간: O(n). 봉우리마다 양쪽으로 걷지만, 각 원소는 한 산의 오르막 또는 내리막에만 속해서 전체 걸음 수는 n 을 넘지 않는다.
• 공간: O(1).

배운 것

"특정 케이스를 어떻게 처리하지"라는 고민이 들면, 케이스를 추가하기 전에 루프의 기준점이 맞는지 먼저 의심하자. 시작점 기준으로는 배열 끝이 특수 케이스였지만, 봉우리 기준으로는 그냥 "내리막이 멈추는 곳" 중 하나였다.