이번 주부터 자료구조를 배우는데요, 오늘은 Stack과 Queue를 배웠습니다. 알고리즘 연습문제를 풀면서 겪었던 오늘의 시행착오를 적어보려고 합니다.🦁


문제

입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.

입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.

  1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
  2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
  3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.

입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.

실패 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const isValid = (str) => {
  const stack = [];

  if (str.length === 0) return false;

  for (const x of str) {
    if (stack.length === 0) stack.push(x);
    else {
      if (
        (stack[0] === '[' && x === ']') ||
        (stack[0] === '{' && x === '}') ||
        (stack[0] === '(' && x === ')')
      ) {
        stack.pop();
      } else {
        stack.push(x);
      }
    }
  }

  return stack.length === 0 ? true : false;
};

실행결과를 보면 1개의 테스트 케이스가 실패한 것을 볼 수 있습니다.

🫥 무엇이 잘못되었을까?

테스트 케이스를 살펴보니 중첩된 괄호의 경우를 생각하지 못했습니다. 무조건 여는 괄호 다음엔 닫는 괄호가 나온다는 생각 때문에 요소를 비교할 때 stack[0]로만 제한을 두고 있습니다. 하지만 여는 괄호 다음에 여는괄호가 나올 수도 있기 때문에 0번째로만 비교해서는 안됩니다.


통과 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const isValid = (str) => {
  const stack = [];

  // ✅ 빈 문자열이면 false로 리턴
  if (str.length === 0) return false;

  for (let i = 0; i < str.length; i++) {
    // 🚧 빈 배열이면 stack에 push 하고 다음 반복문으로 넘어갑니다.
    if (stack.length === 0) {
      stack.push(str[i]);
      continue;
    }

    // 🚧 stack의 마지막 요소와 str[i]가 같으면 stack에서 제거합니다.
    if (
      (stack[stack.length - 1] === '[' && str[i] === ']') ||
      (stack[stack.length - 1] === '(' && str[i] === ')') ||
      (stack[stack.length - 1] === '{' && str[i] === '}')
    ) {
      stack.pop();
      // 🚧 다르다면 stack에 push합니다.
    } else {
      stack.push(str[i]);
    }
  }

  // ✅ 순회 후 stack이 빈 배열이라면 유효한 괄호쌍이므로 true를 반환합니다.
  return stack.length ? false : true;
};

Reference 코드

Reference Code의 Pseudo code는 다음과 같습니다.

  • 최초 입력값이 빈 값이라면 유효하지 않은 괄호쌍으로 간주한다.
  • 각각의 여는 괄호에 알맞는 닫는 괄호를 매칭시키기 위한 괄호맵을 생성한다.
  • str.length만큼 순회한다.
    • 여는 괄호라면 stack에 push한다.
    • 닫는괄호면 stack의 가장 마지막 요소와 그 요소에 대응하는 값을 비교한다.
      • 같다면 stack에서 pop한다.
      • 다르다면 false를 리턴한다.
  • stack이 빈 배열이라면 true를 반환하고 아니라면 false를 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const isValid = (str) => {
  if (str.length === 0) return false;

  // 각각의 여는 괄호에 알맞는 닫는 괄호를 매칭시키기 위한 괄호맵 생성.
  const braketsMap = {
    '(': ')',
    '[': ']',
    '{': '}',
  };

  const arr = str.split('');
  const stack = [];

  for (let i = 0; i < arr.length; ++i) {
    // 1. 여는 괄호 -> stack에 push해야 하는 케이스
    if (arr[i] === '(' || arr[i] === '[' || arr[i] === '{') {
      stack.push(arr[i]);
    } else {
      // 2. 닫는 괄호 -> stack에서 pop해야 하는 케이스

      // 먼저 현재 stack의 가장 위에 위치한 괄호를 확인하고
      const lastElementOfStack = stack[stack.length - 1];

      // 지금 처리해야하는 닫힌 괄호인 arr[i]의 짝과 맞는지를 확인 후 맞지 않다면 false를 리턴하고 로직 전체를 종료
      if (braketsMap[lastElementOfStack] !== arr[i]) return false;

      // 짝이 맞다면 현재 stack의 가장 위에 위치한 괄호를 pop시켜서 stack에서 제거해줌
      stack.pop();
    }
  }

  return stack.length ? false : true;
};

👉🏻 대응하는 값들을 객체로 선언하는 방법이 인상적이었습니다. 저렇게 객체를 만들어놓으면 if문 안에 조건을 여러 개 쓰지 않아도 되는 장점이 있는 것 같습니다. :)