[Stack] 유효한 괄호쌍

유효한 괄호쌍

문제

입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요. 입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.

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

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

입력

인자 1 : str

• string 타입으로 된 문장

출력

• boolean 타입을 리턴해야 합니다.

주의 사항

• 입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
• 입력값으로 들어오는 str의 길이는 0부터 10^4승 까지 입니다.

입출력 예시

const result1 = isValid('[]');
console.log(result1); // true

const result2 = isValid('[)');
console.log(result2); // false

const result3 = isValid('[]{}()');
console.log(result3); // true

const result4 = isValid('[]{)()');
console.log(result4); // false

힌트

• 스택을 사용해 보세요.
• 열린 괄호인 경우 스택에 push합니다.
• 닫힌 괄호인 경우에는 스택의 top을 확인하고, 해당 닫힌 괄호와 짝이 맞는 열린 괄호인지를 확인합니다.

문제풀이

자바스크립트 코드로 괄호가 유효한지 판단하는 방법을 작성하는 경우의 생각 순서는 다음과 같습니다:

1. 주어진 문자열의 길이를 확인합니다.
2. 괄호가 쌍으로 이루어져 있는지 확인하기 위해 스택을 사용합니다.
3. 문자열을 처음부터 끝까지 반복하면서, 여는 괄호일 경우 스택에 push 합니다.
4. 닫는 괄호일 경우, 스택에서 pop을 수행합니다.
5. 스택이 비어있거나 pop한 값과 닫는 괄호가 일치하지 않을 경우, 괄호가 유효하지 않은 것으로 판단하고 false를 반환합니다.
6. 모든 문자열을 반복한 후, 스택이 비어있는지 확인합니다. 스택이 비어있지 않을 경우, 괄호가 유효하지 않은 것으로 판단하고 false를 반환합니다.
7. 스택이 비어있을 경우, 괄호가 유효한 것으로 판단하고 true를 반환합니다.

이 방법을 사용하여 주어진 문자열이 유효한 괄호 문자열인지 판단할 수 있습니다.

const isValid = (str) => {
  // 예외처리 유효한 괄호쌍 입력값이 빈값이라면 유효하지 않은 괄호쌍으로 간주합니다
  if(str === ''){
    return false;
  }

  // 스택 쌓는 빈배열
  const strStack = [];
  // 입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
  // 괄호쌍 저장하는 객채
  const bracketPairs = {
    '(' : ')',
    '{' : '}',
    '[' : ']',
  };
  
  //문자열 순회하며 열린괄호일때 push, 닫힌 괄호일때 top과 매칭되는지 확인
  for(let i = 0; i< str.length; i++){
    // 전체 순회하며 현재 문자 참조할 변수
    const char = str[i]
    // 열린괄호 push
    if(bracketPairs[char]){
      strStack.push(char)
    }else {
      // 닫힌 괄호 top과 매칭
      // 닫힌괄호 나올때 가장 최근에 축가된 괄호 pop하고 닫힌 괄호와 매칭되는 열린괄호인지 검사
      const strStackLast = strStack.pop();
      if(bracketPairs[strStackLast] !== char){
        return false;
      }
    }
  }return strStack.length === 0;
}

bracketPairs 는 왜 필요한가?

  const bracketPairs = {
    '(' : ')',
    '{' : '}',
    '[' : ']',
  };

bracketPairs 객체는 올바른 괄호 문자열인지 판별하기 위해 사용됩니다. 여는 괄호와 닫는 괄호의 쌍을 key-value로 가지는 객체이며, {}, [], ()와 같은 괄호 쌍의 매칭 여부를 확인하는 데 사용됩니다.

예를 들어, 문자열 "([]{})"가 주어졌을 때, 이 문자열이 올바른 괄호 문자열인지 판별하기 위해서는 다음과 같은 방식으로 pairs 객체를 사용할 수 있습니다.

1. "("가 나오면 스택에 push합니다.
2. "["가 나오면 스택에 push합니다.
3. "("가 나오면 스택에 push합니다.
4. ")"가 나오면 스택의 top을 확인하고, top이 "("와 매칭되는지 확인합니다. 매칭되지 않으므로 false를 반환합니다.
5. "["가 나오면 스택의 top을 확인하고, top이 "["와 매칭되는지 확인합니다. 매칭되므로 스택에서 "["를 pop합니다.
6. "{"가 나오면 스택에 push합니다.
7. "}"가 나오면 스택의 top을 확인하고, top이 "{"와 매칭되는지 확인합니다. 매칭되므로 스택에서 "{"를 pop합니다.
8. 스택이 비어있지 않으므로 false를 반환합니다.

따라서, 문자열 "([]{})"는 올바른 괄호 문자열이 아니므로 false를 반환해야 합니다.

레퍼런스코드

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();
        }
    }

    // arr 배열전체를 돌면서 해당 로직을 이행한 후 stack에 어떠한 열린괄호라도 남아있다면 쌍이 맞지 않는 괄호들이 인풋으로 들어왔기 때문에 false를 반환, 그렇지 않고 stack이 비어져 있다면 모든 괄호쌍이 문제없이 유효한 괄호쌍이므로 true를 반환
    return stack.length ? false : true;
};