문제 출처

문제 요약

• N 개의 문자로 구성된 문자열 S가 주어짐
• 문자열 S는 "(", "{", "[", "]", "}" 또는 ")"의 문자로만 구성됨
• 괄호 식이 올바르면 1을, 아니면 0을 return
• N은 [0..200,000] 범위 내의 정수
• 가장 효율적인 알고리즘 작성

문제 풀이

1회 시도

function removeAll(str, c) {
  return str.split(c).join("");
}
function solution(S) {
  if (!S) {
    return 1;
  }

  const counts = {
    "(": 0,
    "{": 0,
    "[": 0,
    "]": 0,
    "}": 0,
    ")": 0,
  };

  S.split("").forEach((e) => {
    ++counts[e];
  });

  if (
    counts["("] !== counts[")"] ||
    counts["{"] !== counts["}"] ||
    counts["["] !== counts["]"]
  ) {
    return 0;
  }

  S = removeAll(S, "()");
  S = removeAll(S, "[]");
  S = removeAll(S, "{}");

  return S === "" ? 1 : 0;
}

• 각 괄호의 개수를 구해서 짝이 안맞으면 0 리턴
• 개수가 맞으면 괄호들을 지워나간다
• 당연히 정답, 퍼포먼스 모두 실패

2회 시도

function removeAll(str, c) {
  return str.split(c).join("");
}

function removeNest(str) {
  if (
    str.indexOf("()") > -1 ||
    str.indexOf("[]") > -1 ||
    str.indexOf("{}") > -1
  ) {
    str = removeAll(str, "()");
    str = removeAll(str, "[]");
    str = removeAll(str, "{}");
    return removeNest(str);
  } else {
    return str;
  }
}

function solution(S) {
  return removeNest(S) == "" ? 1 : 0;
}

• 1회차랑 같은 개념이지만 불필요한 개수 구하기 제거
• 더이상 인접합 괄호가 없을때까지 제거해 나간다.
• 정확도 맞지만 퍼포먼스가 떨어짐

3회 시도

function removeAll(str, c) {
  return str.split(c).join("");
}

function valid(str, start, end) {
  if (str.indexOf(end) < str.indexOf(start)) {
    throw 0;
  }
  if (str.lastIndexOf(end) < str.lastIndexOf(start)) {
    throw 0;
  }
}

function removeNest(str) {
  valid(str, "(", ")");
  valid(str, "[", "]");
  valid(str, "{", "}");
  if (
    str.indexOf("()") > -1 ||
    str.indexOf("[]") > -1 ||
    str.indexOf("{}") > -1
  ) {
    str = removeAll(str, "()");
    str = removeAll(str, "[]");
    str = removeAll(str, "{}");
    return removeNest(str);
  } else {
    return str;
  }
}

function solution(S) {
  try {
    return removeNest(S) == "" ? 1 : 0;
  } catch (e) {
    return e;
  }
}

• 괄호를 제거해 나가는 과정 중에 여는 괄호 닫는 괄호의 위치로 검사하는 로직을 추가한다.
• 조금이라도 루프 횟수가 줄지만 코딜리티 기준 2회 차랑 동일한 퍼포먼스 점수...

마지막

function lastValid(last, c) {
  if (last != c) {
    throw 0;
  }
}

export default function solution(S) {
  try {
    const stack = [];

    for (let i = 0; i < S.length; i++) {
      switch (S[i]) {
        case "(":
        case "{":
        case "[":
          stack.push(S[i]);
          break;
        case ")":
          lastValid(stack.pop(), "(");
          break;
        case "}":
          lastValid(stack.pop(), "{");
          break;
        case "]":
          lastValid(stack.pop(), "[");
          break;
      }
    }

    return stack.length > 0 ? 0 : 1;
  } catch (e) {
    return e;
  }
}

• 결국 구글 신의 도움을 닫았다. 출처 블로그 : https://miiingo.tistory.com/328 (감사합니다 👍)
• 여는 괄호를 스택에 쌓아 가다 닫는 괄호를 만나면 스택의 마지막 요소와 짝이 맞는지 검사하면 된다.
• 코드를 간결하게 하기 위해 throw 와 try catch 로 처리 했다.

결론

• 스택 개념을 응용하는 케이스들을 좀 머리속에 익숙하게 해야 되겠다.