코딩테스트

[Q02] BalancedBrackets

HungryOcto 2023. 1. 11. 00:09

1. 문제

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 합니다.

 

다음 단계에 맞춰 함수를 작성해 보세요.

  • 괄호의 종류를 단 한가지로 한정합니다.
  • 괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
  • 괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

1 - 1) 입력

인자 1 : str

  • string 타입의 괄호가 포함된 문자열

1 - 2) 출력

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

1 - 3) 주의사항

괄호의 종류는 (, )만 고려합니다.
괄호는 먼저 열리고((), 열린만큼만 닫혀야()) 합니다.
빈 문자열을 입력받은 경우, true를 리턴해야 합니다.

1 - 4) 입출력 예시

let output = balancedBrackets('(');
console.log(output); // // -> false

output = balancedBrackets('()');
console.log(output); // --> true

1 - 5) Advanced

모든 종류의 괄호((, ), {, }, [, ])가 포함된 문자열을 입력빋아 모든 괄호의 짝이 맞는지 여부를 리턴해 보세요.

let output = balancedBrackets('[](){}');
console.log(output); // --> true

output = balancedBrackets('[({})]');
console.log(output); // --> true

let output3 = balancedBrackets('[(]{)}');
console.log(output); // --> false

2. 나의 풀이

2 - 1) 코드

제출한 답안

  const balancedBrackets = function (str) {
    let round = 0;
    let curly = 0;
    let square = 0;
  
    for(let i = 0; i < str.length; i++){
      if(str[i] === '(' && round >= 0){
        round++;
      }else if(str[i] === ')' && str[i-1] !== '{' && str[i-1] !== '['){
        round--;
      }else if(str[i] === '{' && curly >= 0){
        curly++;
      }else if(str[i] === '}' && str[i-1] !== '(' && str[i-1] !== '['){
        curly--;
      }else if(str[i] === '[' && square >= 0){
        square++;
      }else if(str[i] === ']' && str[i-1] !== '(' && str[i-1] !== '{'){
        square--;
      }
    }
  
    if(round === 0 && curly === 0 && square === 0) return true;
    else return false;
  };

2 - 2) 코드 + 풀이 과정 1

문제 해결을 위한 아이디어 초안

const balancedBrackets = function (str) {
    // TODO: 여기에 코드를 작성합니다.
    // a. 괄호의 종류를 단 한가지로 한정합니다.
    // 괄호(,)의 개수를 카운트할 변수를 선언
    // 여는 괄호 '(' 일 때 +1, 닫는 괄호 ')' 일 때 -1하여 문자열의 끝에서 해당 변수의 값이 0이면 true를 리턴
  
    let round = 0;
  
    for(let value of str){
      if(value === '('){
        round++;
      }else if(value === ')'){
        round--;
      }
    }
  
    if(round === 0) return true;
    else return false;
 };

2 - 3) 코드 + 풀이 과정 2

2 - 2) 코드를 확장하여 모든 종류의 괄호에 적용해 보았음.

const balancedBrackets = function (str) {
    // b. 괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
  
    let round = 0;
    let curly = 0;
    let square = 0;
  
    for(let value of str){
      if(value === '('){
        round++;
      }else if(value === ')'){
        round--;
      }else if(value === '{'){
        curly++;
      }else if(value === '}'){
        curly--;
      }else if(value === '['){
        square++;
      }else if(value === ']'){
        square--;
      }
    }
  
    if(round === 0 && curly === 0 && square === 0) return true;
    else return false;
};

2 - 4) 코드 + 풀이 과정 3

테스트 실행 후, 출력된 에러 메시지를 바탕으로 2 - 3) 코드를 수정하였음.

const balancedBrackets = function (str) {
    // 2-3)과 같이 작성한 경우
    // 괄호는 먼저 열리고, 열린만큼만 닫혀야 한다는 조건을 만족시키지 못함.
    // 예시 : ')(' 와 같은 입력에도 true를 리턴함.
  
    // 닫힘 괄호가 먼저 들어오는 경우 변수의 값이 -1이 되므로
    // 변수의 값이 0 이상일 때에만 열림 괄호의 수를 변수에 카운트하게 하여
    // 닫힘 괄호가 먼저 들어오는 경우 false를 리턴하게 하였음
  
    let round = 0;
    let curly = 0;
    let square = 0;
  
    for(let value of str){
      if(value === '(' && round >= 0){
        round++;
      }else if(value === ')'){
        round--;
      }else if(value === '{' && curly >= 0){
        curly++;
      }else if(value === '}'){
        curly--;
      }else if(value === '[' && square >= 0){
        square++;
      }else if(value === ']'){
        square--;
      }
    }
  
    if(round === 0 && curly === 0 && square === 0) return true;
    else return false;
};

2 - 5) 코드 + 풀이 과정 최종

테스트 실행 후, 출력된 에러 메시지를 바탕으로 2 - 4) 코드를 수정하였음.

const balancedBrackets = function (str) {
    // 위와 같이 작성하는 경우
    // '[(]{)}' 입력에도 true를 리턴함
    // 어떠한 닫힘 괄호 앞에 다른 종류의 열림 괄호가 오면 안 되도록 코드를 작성하기로 함
    // = 어떠한 닫힘 괄호 앞에 다른 종류의 열림 괄호가 오면, 해당 조건문을 실행하지 않음
    // 위와 같은 코드를 작성하기 위해
    // for of문 대신 for문을 사용하여 str[i-1]과 str[i]의 값을 비교할 수 있도록 코드를 수정
  
    let round = 0;
    let curly = 0;
    let square = 0;
  
    for(let i = 0; i < str.length; i++){
      if(str[i] === '(' && round >= 0){
        round++;
      }else if(str[i] === ')' && str[i-1] !== '{' && str[i-1] !== '['){
        round--;
      }else if(str[i] === '{' && curly >= 0){
        curly++;
      }else if(str[i] === '}' && str[i-1] !== '(' && str[i-1] !== '['){
        curly--;
      }else if(str[i] === '[' && square >= 0){
        square++;
      }else if(str[i] === ']' && str[i-1] !== '(' && str[i-1] !== '{'){
        square--;
      }
    }
  
    if(round === 0 && curly === 0 && square === 0) return true;
    else return false;
  };

3. 레퍼런스 코드 분석

  // naive solution
  // const balancedBrackets = function (str) {
  //   const stack = [];
  //   const opener = '(';
  //   const closer = ')';

  //   for (let i = 0; i < str.length; i++) {
  //     if (str[i] === opener) {
  //       stack.push(str[i]);
  //     } else if (str[i] === closer) {
  //       const top = stack.pop();
  //       if (top !== opener) {
  //         return false;
  //       }
  //     }
  //   }

  //   return stack.length === 0;
  // };

  const balancedBrackets = function (str) {
    // push-pop 개념 적용 (선입후출)
    // stack이란 이름의 배열을 만들고
    // 반복문을 이용, str의 모든 요소를 순서대로 탐색
    // str에 열림괄호가 있는 경우 stack에 해당 값을 보관 (=stack에 보관되는 값은 열림괄호 3종 중 하나)
    // str에 닫힘괄호가 있는 경우 stack의 마지막 값을 꺼내 해당 값과 닫힘 괄호가 같은 종류의 괄호인지 비교 
    // 다른 괄호일 경우 false를 리턴
    // 반복문이 종료되었을 때 stack이 비어있으면 모든 괄호의 짝이 맞은 것이므로 true를 리턴

    const stack = [];
    const opener = {
      '{': '}',
      '[': ']',
      '(': ')',
    };
    const closer = '}])';

    for (let i = 0; i < str.length; i++) {
      // opener의 key에 str[i]와 같은 값이 있다면 = str[i]가 열림괄호라면
      if (str[i] in opener) {
        // 열림괄호를 stack에 push하여 보관
        stack.push(str[i]);
      } else if (closer.includes(str[i])) {
      // str[i]가 닫힘괄호라면
      // stack에 보관된 마지막 값(=열림괄호 3종 중 하나)을 pop하여 변수 top에 할당
        const top = stack.pop();
      // top에 할당한 열림괄호를 key로 갖는 값을 객체 opener에서 찾아 pair에 할당
      // = top에 할당한 열림괄호와 같은 종류의 닫힘괄호를 pair에 할당
        const pair = opener[top];
        // pair와 str[i]가 같은 종류의 닫힘괄호인지 비교하여 
        // 다른 종류의 괄호인 경우 false를 리턴하고 함수 종료
        if (pair !== str[i]) {
          return false;
        }
      }
    }

    // 반복문이 종료 && 함수 종료x && stack이 비어있음 === 모든 괄호의 짝이 맞음
    return stack.length === 0;
};

4. 학습 중 궁금해서 찾아본 부분

  • for...of
    • 개념 : for...of 명령문은 반복가능한 객체 (Array, Map, Set, String, TypedArray, arguments 객체 등을 포함)에 대해서 반복하고 각 개별 속성값에 대해 실행되는 문이 있는 사용자 정의 반복 후크를 호출하는 루프를 생성합니다.
    • 출처 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/for...of
    • 내가 이해한 용도 : 반복가능한 객체의 모든 '속성값'에 대하여 반복문을 수행하고 싶을 때 사용.
                                    (아래 예시에서 variable은 iterable의 속성값을 의미)
    • 사용예
    for (variable of iterable) {
      statement
    }

 

  •  for...in
    • 개념 : for...in문은 상속된 열거 가능한 속성들을 포함하여 객체에서 문자열로 키가 지정된 모든 열거 가능한 속성에 대해 반복합니다. (Symbol로 키가 지정된 속성은 무시합니다.)
    • 출처 : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/for...in
    • 내가 이해한 용도 : 객체의 모든 '키'에 대하여 반복문을 수행하고 싶을 때 사용
                                    (아래 예시에서 variable은 object의 키를 의미)
    • 사용예
for (const variable in object) {
  statement
}

5. 학습 후기

.