[자료구조] Stack을 이용한 괄호 유효성 검사 예제

스택 (Stack)

LIFO (Last In First Out) 구조
가장 마지막에 넣은 걸 먼저 꺼내는 자료구조

 

주요 메서드

 

push(item)	스택에 데이터 추가
pop()	스택에서 데이터 꺼냄 (마지막 값)
peek()	가장 위에 있는 값만 확인 (꺼내진 않음)
isEmpty()	스택이 비었는지 확인
length 또는 size()	현재 스택의 길이 확인

 

JavaScript에는 Stack 자료구조가 따로 없지만, 배열을 통해 구현할 수 있다.
배열에서 Stack의 메소드를 쓰면 스택처럼 동작하는 것!

const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]

console.log(stack.pop());  // 2 꺼냄
console.log(stack);        // [1]

 

스택은 다음 문제들에서 자주 등장한다.

 

- 괄호 유효성 검사
- DFS (깊이 우선 탐색)
- 웹 브라우저 뒤로 가기 기능
- 문자열 뒤집기
- 계산기 구현 (후위 표기법)

---

괄호 유효성 검사 예제

괄호로만 이루어진 문자열이 주어졌을 때, 괄호의 짝이 모두 맞는지 판단하는 함수를 작성하세요.

조건
- 문자열은 오직 (, ), {, }, [, ] 로만 구성됩니다.
- 모든 여는 괄호는 올바른 닫는 괄호로 닫혀야 합니다.
- 괄호는 올바른 순서로 짝지어져야 합니다.

isValid("()")          // true
isValid("()[]{}")      // true
isValid("(]")          // false
isValid("([)]")        // false
isValid("{[]}")        // true

 

이 문제는 스택을 활용해서 풀 수 있다.

function isValid(s) {
  const stack = [];
  const match = new Map([
    ["[", "]"],
    ["{", "}"],
    ["(", ")"]
  ]);

  for (let i = 0; i < s.length; i++) {
    const char = s[i];

    if (match.has(char)) {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (match.get(last) !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Map 객체를 이용해서 풀었다.

여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 마지막에 들어간 여는 괄호를 빼서 합이 맞는지 확인하는 것!

---

Map

JavaScript의 key-value 쌍을 저장하는 객체
일반 객체 {}와 비슷하지만 차이가 있다.

	Map	일반 객체
키 타입	어떤 값도 가능 (객체, 함수, 기본형)	문자열 또는 심벌
키 순서	삽입 순서 유지	보장 안 됨 (ES6 이상 일부 보장)
메서드	.set(), .get(), .has() 등	없음 (직접 프로퍼티 접근)

문자열 뿐만 아니라 어떤 값도 가능하다는 게 큰 장점인 것 같다.
그리고 메서드도 다양해서 키랑 값에 접근해야 할 때 유용하다.

 

Map의 메서드

set(key, value)	키-값 쌍 추가 (또는 갱신)	map.set("a", 1)
get(key)	키에 해당하는 값 반환	map.get("a") // 1
has(key)	해당 키가 있는지 여부 반환 (true/false)	map.has("a") // true

* set()은 중복된 키가 있으면 덮어 씌운다. 

---

그래서 match.has(char)로 여는 괄호인지 확인이 가능하고,
match.get(last)로 닫는 괄호와 여는 괄호가 서로 맞는지 확인할 수 있다.