[CodeKata] 프로그래머스: 2.22(월), 멀쩡한 사각형

🥋 Ooooth!! (Level 2) : 멀쩡한 사각형

코드카타는 계속된다! 문제는 많은데 진도가 늦어 이번주부터는 토요일까지 주 6회로 풀려고 한다.

또한, 저번주에 풀이들이 길어지는 것을 느껴, 최대한 지양하고 싶었지만 우선 일단위로 포스팅하는 것으로 조정해보았다.

 

카카오답게 문제가 매우 길지만, 재귀함수를 통해 괄호쌍을 조정하여 '올바른 괄호 문자열' 로 가공하는 문제이다.

문제의 '용어의 정의' 부분에 로직이 설명되어 있어서, 이를 그대로 코드화하는 데 우선 집중했다.

 

🧮 풀이

function divider(str) {
  let compareCount = 1;
  for (let i = 1 ; i < str.length ; i++) {
    compareCount = str[i] === str[0] ? compareCount += 1 : compareCount-= 1;
    if (compareCount === 0) {
      return { u: str.slice(0, i+1), v: str.slice(i+1) }
    }
  }
}

function isPair(str) {
  let stack = [];
  for (let i = 0 ; i < str.length ; i++) {
    if (str[i] === '(') {
      stack.push(str[i])
    }
    else {
      stack.pop()
    }
  }
  return stack.join('') === '';
}

function solution(p) {
  if (p === '') {
      return '';
  }
  if (isPair(p)) {
    return p;
  }
  else {
    const { u, v } = divider(p);
    let answer;
    if (!isPair(u)) {
      answer = '(' + solution(v) + ')';
      for (i=1 ; i < u.length-1 ; i++) {
        answer += u[i] === '(' ? ')' : '(';
      }
    }
    else {
      answer = u + solution(v)
    }
    return answer
  }
}

1. 개별기능 함수 만들기

• divider(): 괄호 문자열을 인자로 받아 u(균형잡힌 괄호 문자열), v(나머지) 로 잘라주는 함수, 비구조화를 위해 객체로 반환
• isPair(): 괄호 문자열이 균형잡힌 괄호 문자열인지 검사하는 boolean 함수, 균형이 안맞다면 stack 에 '(' 남게됨

2. 괄호 문자열(p) '균형잡힌 괄호 문자열' 확인

• p가 빈 문자열일 때 예외처리를 해준다. ('' 대신 p 반환해도 됨. isPair() 검사와 if로 묶어 p를 반환해도되나 직관성을 위해 분리)
• isPair() 검사를 통해, p가 균형잡힌 괄호 문자열이라면 바로 반환하고 종료하면 된다.

3. 괄호 문자열(p) 분할 및 가공

• 아니라면, divider() 를 통해 p를 u, v로 분리해준다.(비구조화) answer는 문제로직에 따라 가공될 새로운 괄호 문자열
• u가 isPair() 거짓인 경우, '(' + v에 대한 재귀 + ')' 순으로 더한다. (solution(v)를 통해 solution() 함수를 재귀함수로 활용)
• 이후, u의 양 끝을 제외한 나머지 괄호를 뒤집어서 더해야하므로, 1 ~ (length-1) 전까지 순회하며 위처럼 뒤집었다.
• u가 isPair() 참인 경우, u와 v에 대한 재귀를 더한 값이 answer 가 된다.

 

🖇 리뷰

function solution(p){
  if(p === "")
    return p;
  
  let leftBrkNum = 0;
  let rightBrkNum = 0;
  let pIdx = 0;
  let result = '';
  let isRight = true;

  do{
    if(p[pIdx] === '(')
      leftBrkNum++;
    else
      rightBrkNum++;
    if(rightBrkNum > leftBrkNum)
      isRight = false;
    pIdx++;
  }while(leftBrkNum !== rightBrkNum)

  let u = p.substr(0, pIdx);
  let v = p.substr(pIdx);

  if(isRight){
    return u + solution(v);
  }
  else{
  u = u.substr(1,u.length-2).replace(/[\(]|[\)]/g, (a) => a === ')' ? '(' : ')');
  v = `(${solution(v)})`;
    return v + u;
  }
}

* 출처: taesung 님의 블로그 (taesung1993.tistory.com/m/28?category=868017 )

 

전반적인 풀이는 크게 다르지 않다.

균형잡힌 괄호 문자열을 확인하기 위해 위처럼 do - while 반복문을 사용하는 방법도 있다는 것을 알았다.

또한, 정규식 + replace() 조합을 통해 괄호 방향을 바꾼 것이 매우 좋은 방법이라고 생각한다.

 

 

좋은 풀이도 많이 있었지만, 나 역시 문제에 제시된 기능들을 각각 함수화하고 재귀를 활용해 푼 점이 매우 뿌듯하여 리뷰를 이정도로 마치겠다. 😃😃