Online Stock Span: 코딩 문제 풀이

Source: Dev.to

번역을 진행하려면 번역하고자 하는 전체 텍스트(코드 블록을 제외한 본문)를 제공해 주시겠어요? 텍스트를 받는 대로 원본 형식과 마크다운을 유지하면서 한국어로 번역해 드리겠습니다.

문제 개요

Online Stock Span은 데이터를 점진적으로 처리하면서 과거 정보를 스마트하고 압축된 형태로 유지할 수 있는지를 테스트하는 스트리밍‑스타일 문제입니다. 매일의 주가를 하나씩 제공받으며, 새로운 가격이 들어올 때마다 그 가격의 스팬을 계산해야 합니다.

주가의 스팬은 해당 일의 가격보다 작거나 같은 가격이 연속해서 나타난 일수(오늘을 포함)를 의미합니다.
예를 들어, 오늘의 가격이 어제와 그 전날보다 높다면 스팬은 그 모든 날을 포함합니다. 오늘의 가격이 어제보다 낮다면 스팬은 단지 1이 됩니다.

핵심 제약은 이것이 온라인 문제라는 점입니다. 미래의 가격을 볼 수 없으며, 각 쿼리가 들어올 때마다 즉시 답해야 합니다. 이것이 전통적인 배열 기반 주가 문제와 다른 점입니다.

왜 단순한 접근법이 실패하는가

직관적인 방법은 오늘부터 뒤로 돌아보면서 연속된 이전 가격들이 현재 가격보다 작거나 같은 경우를 세는 것입니다.
이는 하루에 대해서는 작동하지만, 가격이 계속 상승하면 매번 점점 더 멀리까지 스캔하게 됩니다. 최악의 경우 이는 이차 시간 복잡도로 이어집니다.

면접관은 이 문제를 통해 여러분이 중복 작업을 피하고 불필요한 비교를 “건너뛸” 수 있는 패턴을 인식할 수 있는지를 확인합니다.

해결책의 핵심 아이디어

핵심 통찰은 모든 이전 날짜가 동일하게 중요한 것이 아니라는 점입니다.

가격이 더 낮은 이전 날짜가 있고, 그보다 높은 가격을 가진 더 최신 날짜가 있다면, 그 이전 날짜는 단독으로는 다시는 중요하지 않게 됩니다. 더 최신의 높은 가격에 의해 “덮어씌워”지기 때문입니다.

이 관찰은 단조 스택(monotonic stack) 을 사용하는 아이디어로 바로 이어집니다.

더 많은 코딩 문제 풀이를 탐색하고 싶으신가요? Binary Tree Zigzag Level Order Traversal와 Binary Search Tree Iterator를 확인해 보세요.

스택 기반 접근 방식 작동 원리

1. 스택을 유지합니다. 각 항목은 이전 날짜를 나타내며 다음을 저장합니다:

   • 가격
   • 해당 가격에 대한 스팬
     스택은 가격이 하단에서 상단으로 엄격히 감소하는 순서로 유지됩니다.

2. 새로운 가격이 들어오면 오늘에 대한 스팬을 1로 시작합니다.

3. 스택의 최상단을 확인합니다:

   • 최상단 가격 ≤ 오늘 가격이면, 오늘 스팬에 그 항목이 나타내는 모든 날을 포함합니다. 그 항목의 스팬을 오늘 스팬에 더하고 해당 항목을 팝합니다.
   • 스택이 비거나 최상단 가격 > 오늘 가격이 될 때까지 반복합니다.

4. 오늘 가격과 계산된 스팬을 스택에 푸시합니다.

5. 방금 계산한 스팬이 오늘의 답이 됩니다.

왜 이것이 개념적으로 작동하는가

각 스택 항목은 스택에서 아래에 있는 가격보다 모두 작은 연속된 일수 블록을 나타냅니다.
스팬을 팝하고 병합함으로써, 여러 작은 일수를 하나의 항목으로 압축합니다. 이는 동일한 일수를 반복해서 스캔하는 것을 방지합니다.

각 날짜의 가격은 스택에 한 번 푸시되고 최대 한 번 팝되므로, 가격이 상승하는 긴 시퀀스에서도 효율성을 보장합니다.

Why this is efficient in practice

하루에 스택에서 여러 번 팝이 발생할 수 있지만, 그 팝은 하루마다 반복되지 않습니다.
전체 가격 시퀀스를 살펴보면 푸시와 팝의 총 횟수는 linear입니다. 이는 개별 단계가 더 복잡해 보일지라도 연산당 평균 시간이 일정함을 의미합니다.

이 “amortized” 효율성은 면접관이 자주 듣고 싶어 하는 개념입니다.

후보자들이 흔히 저지르는 실수

• 가격만 저장하고 스팬을 수동으로 다시 계산하는 경우, 압축의 이점을 잃게 됩니다.
• 비교 조건을 오해함: 문제에서는 명시적으로 “보다 작거나 같음”이라고 되어 있는데, “보다 작음”만 사용하면 잘못된 결과가 나옵니다.
• 이것이 온라인 문제라는 점을 잊고 전체 배열을 미리 처리하려 하면 질문의 요점을 놓치게 됩니다.