2020 카카오 블라인드채용 문제이며 레벨2로 분류되어있는 문제이다.

문제

지금까지 풀어봤던 문제 중 가장 지문을 여러번 읽어본 문제이다.

풀이과정

<입력>

1. 괄호문자열 "p"(String)

<재귀>

균형잡힌 괄호문자열을 올바른 괄호문자열로 변경하는 알고리즘에 이미 명시된 "재귀적으로" 라는 말에서 이 문제는 재귀함수를 써야하는구나 라는것을 알 수 있다.
즉,

function 함수( str ){
실행할 알고리즘
함수( str` )
return result
} 

의 형태가 될것이다.

또한 문자열이 공백이면 공백을 반환하고
처음 입력받은 값을 나누어 앞을 'u' 뒷부분을 'v'라고 할 경우
'u'는 조건에따라 처리방식이 다르며, v 부분을 재귀적으로 처리하게되므로 위 함수를 더 세밀하게 표현하면

function 함수( str ){
if(str==='')return ''
let u = str앞부분
let v = str뒷부분
if(조건 true){
return u+함수(v)
} else{
return '('+함수(v)+')'+(u앞뒤자르고'('와')'서로 바꾼것)
}
}

가 될것이다.
문제에서 과정 1~4로 설명된 과정을 코드로 요약해둔것이다.

여기서 추가적으로 필요한것은
1. 앞부분 뒷부분을 나누는 방법
2. 5번째줄 if에 들어가는 조건 판별
3. 밑에서 2번째 줄 앞뒤 자르고 뒤집기 도구
정도가 될것이다.

<앞부분 뒷부분 나누기>

문자열 앞부분과 뒷부분 나누는 방법은 u를 '최소의 균형잡힌 문자열'로 만드는것이다.
균형잡힌 문자열이란 '('와')'의 갯수가 같은것이므로 다음과 같이 정의해주겠다

function balanceCheck (str){
    let map = new Map()
    for(const char of str){
        map.set(char,map.get(char)+1||1) //'('와 ')'의 갯수 저장
    }
    return map.get("(")==map.get(")")    //'('와')'의 갯수가 같으면 true 아니면 false 반환
}

<올바른 문자열 판별>

그리고 u의 처리를 위한 조건 판별은 "u가 올바른 문자열인가"이다.
사실 나중에 알게된 사실인데 '최소의 균형잡힌 문자열'에서는 제일 앞의 문자가 '('라면 항상 올바른 문자열이 되기 때문에, 문자열에 앞에서부터 한 괄호씩 추가해가며 검사하여 처음으로 '균형잡힌 문자열'이 되었을 때 제일 첫 괄호가 '('일 경우 true로 정의해주면 되는것이었지만, 거기까지 생각이 닿지 않았다. 입력하는 문자열의 '올바른 문자열' 판별 함수를 만들어보았다.

function perfectCheck(str){
    let result = true
    let stack = []
    for(const char of str){
        if(char==="("){
            stack.push(char)
        } else {
            if(!stack){
                result = false
                break;
            } else if(stack[stack.length-1]=="("){
                stack.pop()
            }
        }
    }
    return stack.length>0?false:result
}

<문자열 변환>

입력한 문자열을 앞뒤 한개씩 자르고 '('와')'를 서로 바꾸는 함수이다.

function reverse(str) {
    let arr = str.slice(1, str.length - 1).split(""); //2번째부터 마지막에서 2번째까지 자르고 배열화
      for(let i=0;i<arr.length;i++){
                if(arr[i]==='(') arr[i]=')'  //'('는 ')'로
                else arr[i]='('              //')'는 '('로 변환
            }
  return arr.join("");
}

<함수 조립하기>

이제 주어진 도구들로 메인 함수에서 문제를 해결한다.
원래 우리가 목표로 했던 코드 구조가

function 함수( str ){
if(str==='')return ''
let u = str앞부분
let v = str뒷부분
if(조건 true){
return u+함수(v)
} else{
return '('+함수(v)+')'+(u앞뒤자르고'('와')'서로 바꾼것)
}
}

였던것을 생각해보자

function solution(p) {
  if (p=='') return "";                     //입력이 공백이면 공백 반환
           
  let current = p[0]                        //입력의 첫 괄호부터
  let idx = 1
  while(!balanceCheck(current)){            //균형잡힌 괄호열이 될때까지
        current+=p[idx]                     //입력 문자열의 괄호 하나씩을 추가
        idx++
    }

  const u = p.slice(0, idx);                  //균형잡힌 괄호문자열 앞부분
  const v = solution(p.slice(idx, p.length)); //뒷부분을 재귀로 불러온다

  if (balanceCheck(u)&&u[0]=='(') return u + v; //앞부분이 균형+제일앞이 '('라면 올바른 문자열이고 u+재귀로 처리한 뒷부분을 반환
  else return "(" + v + ")" + reverse(u);  // 아니라면 괄호안에 재귀로처리한 v를 넣고 뒤에는 u를 가공하여 추가
}

괄호문자열 앞뒤를 나누는 부분에 조금 복잡한 부분이 추가되었을 뿐 제일 처음 계획한 코드와 꽤 유사하게 되었다.
결과는?

제일 처음 풀었을때는
if (balanceCheck(u)&&u[0]=='(')
이부분이 if(perfectCheck(u))였고 코드 전체로보면 perfectCheck(u) 함수 구현이 추가되어있었다.
크게 시간이 많이 차이나지는 않았지만 코드를 간결하고 가독성있게 만드는데 조금 더 신경을 써야겠다는 생각이 들었다.

<전체코드>

function balanceCheck (str){
    let map = new Map()
    for(const char of str){
        map.set(char,map.get(char)+1||1)
    }
    return map.get("(")==map.get(")")
}

function reverse(str) {
    let arr = str.slice(1, str.length - 1).split("");
      for(let i=0;i<arr.length;i++){
                if(arr[i]==='(') arr[i]=')'
                else arr[i]='('
            }
  return arr.join("");
}

function solution(p) {
  if (p=='') return "";
          
  let current = p[0]
  let idx = 1
  while(!balanceCheck(current)){
        current+=p[idx]
        idx++
    }

  const u = p.slice(0, idx);
  const v = solution(p.slice(idx, p.length));

  if (balanceCheck(u)&&u[0]=='(') return u + v;
  else return "(" + v + ")" + reverse(u);
}