LeetCode 문제를 풀기 시작했을 때 각각 새로운 세계를 발견하는 기분이었습니다. 시간이 좀 걸렸지만 대부분의 문제가 구조로 그룹화되어 있다는 것을 깨달았습니다. 패턴을 인식하면 문제는 스스로 해결됩니다. 오늘은 스택의 차례입니다.

이전 글에서 스택이 어떻게 작동하는지 살펴보았습니다. 오늘은 그 기초를 이용해 세 가지 클래식한 문제를 해결합니다.

다음을 찾을 수 있습니다:

• 단계별로 해결된 세 가지 문제: 균형 잡힌 괄호, 문자열 뒤집기 및 경로 단순화
• 스택이 면접 외에서 어디에 나타나는지

빠른 기억

LIFO: 마지막에 들어간 것이 첫 번째로 나옵니다. push 꼭대기에 추가합니다.pop에서 최상위를 제거합니다. JavaScript에서 배열은 이미 스택처럼 동작합니다. 전체 세부 정보가 필요하시면 이전 기사에서 찾을 수 있습니다..

이제 문제들로 넘어가겠습니다.

문제 1: 균형 잡힌 괄호

"Valid Parentheses" (LeetCode).

문제: 문자열s이 주어졌을 때,()[]{}가 유효한지 확인하세요. 각 열리는 부분에는 해당하는 닫힘과 올바른 순서가 있어야 합니다.

Input:  "()[]{}"   → true
Input:  "([)]"     → false
Input:  "{[]}"     → true

어떻게 생각했나요?

"가장 나중에 열린 것은 가장 먼저 닫혀야 합니다." 정확히 그것이 스택이 잘하는 일입니다.

문자열을 순회합니다. 각 열린 괄호는 스택에 추가됩니다. 각 닫힌 괄호는 스택의 최상위와 일치해야 합니다. 만약 마지막에 스택이 비어있다면, 모든 괄호가 올바르게 닫혔습니다.

해결책

function validParentheses(s) {
  const stack = [];
  const pairs = { ")": "(", "}": "{", "]": "[" };

  for (const char of s) {
    if (char === "(" || char === "{" || char === "[") {
      stack.push(char);
    } else if (stack.pop() !== pairs[char]) {
      return false;
    }
  }

  return stack.length === 0;
}

중요한 점:

1. pairs각 닫힌 괄호를 그에 해당하는 열린 괄호와 매핑합니다.
2. 열린 괄호는 스택에 추가되고, 닫힌 괄호는 pop를 수행하고 유효성을 검사합니다.
3. 스택이 비어 있으면 pop을 수행할 때 undefined을 반환하고 비교가 실패합니다. 편리하게, 그래서 추가적인 확인이 필요 없습니다.
4. 마지막으로 스택은 비어 있어야 합니다.

복잡성: O(n) 시간과 O(n) 공간.

문제 2: 문자열 뒤집기 (쉬움)

LeetCode의 "Reverse String"의 변형입니다.. 스택을 사용하여 단어를 뒤집을 거예요.

문제: 문자열 s을 주면, 뒤집힌 문자열을 반환하세요.

Input:  "stack"   → "kcats"
Input:  "hello"   → "olleh"

어떻게 생각해요?

"뒤집기"가 힌트입니다. 요소를 순서대로 넣고 역순으로 꺼냅니다. 그것이 바로 스택이 하는 일입니다.

실제로는 사용하시겠습니까s.split("").reverse().join("")준비되었습니다. 여기서는 스택을 사용하여 패턴이 작동하는 것을 보여줍니다.

해결책

var reverseString = function (s) {
  const stack = [...s]; // crea un stack con los caracteres
  let reversed = "";

  while (stack.length > 0) {
    reversed += stack.pop();
  }

  return reversed;
};

모든 문자를 스택에 넣고 하나씩 꺼냅니다. 그래서pop가장 최근에 들어온 것을 반환하고, 문자가 뒤집혀 나옵니다.

복잡도: O(n) 시간과 O(n) 공간.

문제 3: 경로 간소화 (중급)

"경로 간소화" (LeetCode).

문제: Unix의 절대 경로를 표준 형태로 변환합니다.

규칙:

• . 현재 디렉토리입니다.
• .. 한 단계 올라갑니다.
• //는 /로 처리됩니다.
• 결과는 / 에서 끝나지 않으며, 뿌리를 제외합니다.

Input:  "/home//foo/"       → "/home/foo"
Input:  "/../"              → "/"
Input:  "/a/./b/../../c/"   → "/c"

어떻게 생각해요?

..은 무엇을 합니까? 이전 디렉토리로 돌아갑니다. 그곳에 신호가 있으니, 우리는 어떻게 지나갔는지 기억하고 돌아갈 수 있어야 합니다.

경로를 나눕니다/를 각 구성 요소를 순회합니다:

• "" 또는 "."를 무시합니다.
• ".."를 스택에서 제거합니다.
• 어떤 다른 것도 디렉토리이며 스택으로 이동합니다.

마지막으로, 스택에는 단순화된 경로의 디렉토리가 포함됩니다.

솔루션

var simplifyPath = function (path) {
  const stack = [];

  for (const part of path.split("/")) {
    if (part === "" || part === ".") continue;
    if (part === "..") stack.pop();
    else stack.push(part);
  }

  return "/" + stack.join("/");
};

팁: JavaScript에서, pop가 비어 있는 스택에 대해 아무것도 깨뜨리지 않고 오직 undefined를 반환합니다. 따라서 경로가 루트를 넘어 올라가려고 하더라도 추가적인 검증은 필요 없습니다.

복잡성: O(n) 시간과 O(n) 공간.

세 가지 뒤에 숨겨진 패턴

만약 이것들을 차례대로 읽으면 같은 점을 알게 될 것입니다. 세 가지 모두 같은 근본적인 문제를 해결합니다. 이전 상태로 돌아갈 수 있도록 하는 것입니다.

• 균형 잡힌 괄호: 마지막 열린 괄호를 기억하여 닫힘을 검증합니다.
• 문자열 반전: 반대 순서로 돌아갑니다.
• 경로 단순화: .. 한 단계 뒤로 돌아갑니다.

Ese es 스택의 초능력. 문제가 마지막을 기억하도록 요청하거나, 무언가를 되돌리거나, 뒤에서 앞으로 처리하도록 요청할 때 거의 항상 답은 스택입니다.

인터뷰를 넘어선 스택

스택은 인터뷰의 순수한 사안이 아닙니다. "돌아가기" 패턴이 어디에나 나타납니다:

• 웹 브라우저의 돌아가기 버튼은 스택입니다.
• 당신의 에디터의 undo/redo도 마찬가지입니다.
• 어떤 언어의 호출 스택(그래서 스택 오버플로우 오류가 발생하는 이유)입니다.
• 데이터 파이프라인은 마지막으로 본 내용의 맥락을 유지해야 합니다.

연습을 계속하기 위해

LeetCode의 난이도별 문제:

1. 최소 스택easy.
2. 야구 게임easy.
3. 리버스 포스기슈 표현식을 평가 medium.
4. 일일 온도 medium. 이는 단조 스택 패턴의 소개입니다.

어느 것이 더 어려웠나요? 댓글에 알려주세요. 나에게 Simplify Path는 해결하기 위해 더 많은 고생을 했습니다.