[프로그래머스] 괄호 회전하기 - javascript

📖 문제링크

https://programmers.co.kr/learn/courses/30/lessons/76502

문제 설명

올바른 괄호 문자열은 (), {}, [] 이다.
문자열을 왼쪽으로 x칸씩 회전해서 올바른 괄호 회전열의 개수를 구하라는 것이 간단히 설명한 문제의 설명이다.

• s의 길이는 1~1000이다.

👨‍💻 문제풀이

필자가 푼 문제풀이

function solution(s) {
    const stack = [];
    let result = 0;
    let isRight = true;
    if (s.length % 2 === 1) return 0;

    for (let i = 0; i < s.length; i++){
        let candidate = s.slice(i) + s.slice(0, i);
        isRight = true;
        for (let word of candidate) {
            if (word === "(" || word === "{" || word === "[") stack.push(word);
            else {
                let leftWord = stack.pop();
                if (word === ")" && leftWord === "(") continue;
                if (word === "}" && leftWord === "{") continue;
                if (word === "]" && leftWord === "[") continue;
                isRight = false;
                break;
            }
        }
        if (isRight) result++;
    }
    return result;
}

처음에는 완전탐색이라고 생각하여 재귀함수를 이용해 풀고 있었다.

하지만 테스트 상에서 시간 복잡도가 너무 많이 나오는 것을 볼 수 있었다.

그래서 stack을 이용해 왼쪽 괄호일 때는 stack에 넣고 오른쪽 괄호일 때는 stack에서 괄호를 빼 올바른 괄호인지 확인 후 맞다면 계속 for문을 돌고 아니라면 for문을 탈출하여 시간을 단축했다.

2022.02.06