몸과 마음이 건전한 SW 개발자

프로그래머스 [Lv. 2] 괄호 변환 {언어 : JavaScript} 본문

알고리즘/풀었지만 다시 보기

프로그래머스 [Lv. 2] 괄호 변환 {언어 : JavaScript}

스위태니 2024. 11. 18. 13:22

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60058

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

정답 코드

function solution(p) {
    const isValid = (string) => {
        const stack = [];
        for (let idx = 0; idx < string.length; idx++) {
            if (stack.length) {
                if (string.at(idx) === ")" && stack.at(-1) === "(") {
                    stack.pop();
                } else {
                    stack.push(string.at(idx));
                }
            } else {
                stack.push(string.at(idx));
            }
        }
        return stack.length ? false : true;
    }
    
    const turnString = (string) => {
        const stack = [];
        for (let idx = 0; idx < string.length; idx++) {
            if (string.at(idx) === "(") {
                stack.push(")");
            } else {
                stack.push("(");
            }
        }
        return stack.join("");
    }
    
    const dfs = (string) => {
        if (string.length === 0) {
            return "";
        }
        let balance = 0;
        let newString = "";
        for (let idx = 0; idx < string.length; idx++) {
            if (string.at(idx) === "(") {
                balance += 1;
            } else {
                balance -= 1;
            }
            if (balance === 0) {
                if (isValid(string.slice(0, idx+1))) {
                    newString += string.slice(0, idx+1) + dfs(string.slice(idx+1));
                } else {
                    newString += "(" + dfs(string.slice(idx+1)) + ")" + turnString(string.slice(1, idx));
                }
                break;
            }
        }
        return newString;
    }
    
    const answer = dfs(p);
    return answer;
}

풀이 방법

  1. 괄호가 올바른 괄호 문자열인지 확인하는 함수와 문자열 전부를 뒤집어 주는 함수를 만들었다.
  2. dfs를 살펴보면
    1. 빈 문자열은 그대로 반환한다.
    2. 매개변수 설명을 보면 일단 p가 무조건 짝수이다.
    3. balance가 0인 경우 일단 균형잡힌 괄호 문자열이다.
      1. 따라서 현재 idx까지의 문자열이 올바른 괄호 문자열인지 확인한다.
        1. 올바른 괄호 문자열이면
          1. newString에 더해준다.
          2. 이후 idx 뒷 부분(v부분)을 잘라서 재귀를 돌린다.
        2. 아닌 경우
          1. "("를 더해주고
          2. idx 뒷 부분(v부분)을 잘라서 재귀를 돌린다.
          3. 이후 ")"를 더해준 다음 0부터 idx까지의 부분(u부분)을 다시 자른다.
            1. u부분의 앞 뒤를 문자를 제거한다.
          4. u부분의 나머지 문자열을 전부 뒤집는다.
    4. 재귀가 끝나고 newString을 반환하면 끝! 

느낀점

  • 오랜만에 다시 푸는데 오래 걸리는 것을 봐서는 천천히 접근을 할 필요가 있다.
  • 다시 풀었다고 자만하지 말고 여러 번 다시 풀어 보자.