🔎 괄호 변환

❓ 문제링크

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

📄 제출 코드

// 균형잡힌 : ()개수 같은거
// 올바른 : ()가 옳게 닫힌거
function solution(p) {
  let chk = 0;
  let u = '';
  let v = '';
  let flag = true;
  // 1단계 : 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
  if (p.length == 0) return '';
  else {
    // 2단계 : 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
    for (let i = 0; i < p.length; i++) {
      switch(p[i]){
        case '(':
          u += p[i];
          chk++;
          break;
        case ')':
          u += p[i];
          chk--;
          if (chk < 0) flag = false;
          break;
      }
      if (chk == 0) {
        v = p.substring(i + 1);
        break;
      }
      // console.log(`chk:${chk}`);
    }
    console.log(`u: ${u} , v:${v}`);

    // 3단계 : 올바른이면, v에 대해 1단계부터.
    // 3-1. 수행결과 문자열을 u에 이어붙여 반환
    if (flag) return u += solution(v);
    // 4단계
    else {
      // 4-1,4-2,4-3 : 앞뒤로 ()붙이고, v에대해 1단계부터 수행한거 반환
      let tmp = '(' + solution(v) + ')';
      // 4-4. u의 첫 마지막 문자제거. 
      u = u.substring(1, u.length - 1);
      
      // 나머지 문자열 뒤집기
      tmp += u.split('').map(el => { return el == '(' ? el = ')' : el = '('}).join('')
      // 4-5. 반환.
      return tmp;
    }
  }
}
let p = "()))((()";
console.log(solution(p));

이 문제는 되게 오래걸렸는데 구현도 구현이지만 문제 이해가 안되서 오래 걸렸다..
30 -40분을 문제이해하는데 쓰다보니까 그냥 적힌대로 단계별로 구현해야겠다고 생각이 들었다.
그래서 왼쪽에 메모장으로 조건 적어놓고 보면서 풀었다. 😠

**조건**
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

👉 1단계

입력이 빈 문자열의 경우 빈 문자열을 반환.

	if (p.length == 0) return '';

간단하게 p문자열길이가 0이면 바로 빈 문자열을 리턴했다.

👉 2단계

두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
문제에서 올바른 괄호랑 균형잡힌 괄호란 용어가 나오는데 구분하자면

• 균형잡힌 : ()개수 같은거
• 올바른 : ()가 옳게 닫힌거

for (let i = 0; i < p.length; i++) {
  switch(p[i]){
    case '(':
      u += p[i];
      chk++;
      break;
    case ')':
      u += p[i];
      chk--;
      if (chk < 0) flag = false;
      break;
  }
  if (chk == 0) {
    v = p.substring(i + 1);
    break;
  }
  // console.log(`chk:${chk}`);
...

p[i]의 상태에 따라 먼저 u에 추가하고 올바른 괄호인지 체크할 chk변수를 증가감소시킨다.
만약 )가 나왔을 때 chk가 음수가 된다면, flag는 false로 두고, 다음 반복을 한다.
chk가 0이 됐을때 옳게 닫힌 괄호이므로, v에 나머지 글자들을 담아두어 u와 v를 나눈다.

👉 3단계

문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1 : 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

if (flag) return u += solution(v);

2단계에서 flag로 올바른 괄호인지 아닌지 판단했다.
여기서 주목할건 v에 대해 1단계부터 다시 수행합니다라는 구문이다.
이 부분은 재귀를 하면 된다는 소리고, solution(v)를 넣어 재귀를 돈다.
그래서 u에 solution(v)를 더해서 값을 리턴하면된다.

👉 4단계

문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1~3 : solution(v)의 앞뒤로 (와 )를 붙입니다.

let tmp = '(' + solution(v) + ')';

4-4 : u의 첫번째와 마지막문자를 제거하고, 나머지 문자열의 괄호방향을 뒤집어 뒤에 붙입니다.

u = u.substring(1, u.length - 1);
tmp += u.split('').map(el => { return el == '(' ? el = ')' : el = '('}).join('')

처음에 배열로 변환해서 unshift pop을 한다음 join을 생각했는데, 앞에서 풀었던 문자열압축에서 substring이 생각이 났다.
앞뒤를 제거한다는게 결국 두번째인덱스부터 뒤에서두번째인덱스까지 문자열을 출력한다는거니까 substring을 사용해 한번에 값을 구했다.

괄호방향을 뒤집는다는건 reverse가 아니라 그냥 한글자씩 비교하여 (면 ) , )면 (로 변경하라는 소리다.
처음엔 replace로 바꾸려다가 작성하면서 든 생각이 먼저 (를 )로 바꾸면 남은 문자열은 결국 ))))... 가되서 결과가 ((((...로 나올거란 생각이 들었다.
그래서 for문으로 바꾸었다가 map을 사용해보고 싶어서, map을 이용해 바꾼 새로운 배열을 join('')으로 묶어 값을 반환했다.