[2020 KAKAO BLIND RECRUITMENT] 괄호 변환 (with Javascript)

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

코딩테스트 연습 - 괄호 변환

 

이 문제는 2020 카카오 블라인드 채용에서 1차 코딩테스트로 나온 문제이다.

 

나는 아래와 같은 단계로 풀었다.

 

1. 올바른 괄호 문자열 확인하는 함수 작성

2. 균형잡힌 괄호 문자열인지 확인하는 함수 작성

3. 그리고 나머지 문제 자체에서 설명하는대로 로직 작성

 

문제 보면 로직을 친절하게도 하나하나 다 설명해줘서 1. 문자열 압축 문제보다 쉬웠던 것 같다.

 

1. 올바른 괄호 문자열 확인 함수

// 올바른 괄호 문자열인지 확인하는 함수
function isCorrectString(n) {
  if (n === '') return true;

  const array = n.split("")
  const list = [array[0]];

  function isClose(now, curr) {
    if (now === '(' && curr === ')') return true;
    return false
  } 
  
  for (let i = 1; i < array.length; i++) {
    if (isClose(list[list.length - 1], array[i])) {
      list.pop();
    } else {
      list.push(array[i])
    }
  }

  return list.length === 0
}

함수 구조는 아래와 같다.

1. 문자열을 받아서 그 문자열을 각각의 문자 하나를 인자로 가지는 배열로 만든다. (split 메서드 이용)

2. list란 이름의 배열 하나를 넣고 for문을 돌면서 list 안에 있는 괄호를 닫을 수 있는지 없는지 여부에 따라서 list에 있는 내용을 빼거나 닫을 수 없으면 해당 요소를 추가하는 식이다.

3. 이 함수는 list의 길이가 0인지 아닌지를 리턴한다. 0이면 올바른 괄호 문자열이다.

 

exam ) '(())' 이라는 문자열이 들어온다고 하자, 이 문자열은 올바른 괄호 문자열이다. 함수 내에서는 아래와 같은 일이 일어난다.

1. ['(', '(', ')', ')'] 배열로 만들어지고, 이 배열을 for문으로 순회한다.

2. 순회 전에 맨 처음에 위 배열의 첫번째 인자를 list에 넣어둔다.

3. for 문은 index 1부터 시작하여, 배열의 두번째 인자부터 비교하면서 돌도록 한다. ( 이 예제에서는 총 3번 돔)

- 1 순회 시 now는 ( 이고 curr는 ( 이므로 그냥 (를 push한다. (list 배열은 [ (, ( ] 인 상태)

- 2 순회 시 now는 ( 이고 curr는 ) 이므로 list를 pop 한다 (마지막 인자를 뺀다. list는 [ ( ] 상태 )

- 3 순회 시 now는 ( 이고 curr는 ) 이므로 list를 pop 한다. (마지막 인자를 뺀다. list는 [] 즉 빈 배열로 돌아간다.)

 

4. 빈 배열의 길이는 0 이므로 true를 리턴하게 된다. 

 

이런 일을 하게되는 함수이다.

 

2. 균형 잡힌 괄호 문자열 확인 함수

function isValenceString(n) {
  if (n === '') return true;

  const array = n.split('');
  return array.filter(value => value === '(').length === array.filter(value => value === ')').length
}

이건 그냥 문자열에 (와 ) 갯수가 똑같은지를 확인하는 함수다.

 

 

3. 실제 로직 풀이

function solution(p) {
  if (p === '') return '';

  // 1. 균형잡힌 괄호 최소 문자열과 u와 나머지 v로 문자열을 나눈다.
  let limit = p.length;
  let u, v;
  for (let i = 2; i <= p.length; i += 2) {
    u = p.slice(0, i)
    if (isValenceString(u)) {
      limit = i;
      break;
    }
  }
  v = p.slice(limit)
  if (isCorrectString(u)) {
    return u + solution(v)
  } else {
    let uList = u.split('')
    uList.shift();
    uList.pop();

    let string = ''
    string += '(' + solution(v) + ')' + changeTag(uList.join(''));
    return string;
  }
}

사실 이부분은 설명을 하기 애매한게 말 그대로 문제에 아래처럼 나와있다. 위 함수는 이것을 코드화 한 것 뿐이다.

 

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. 생성된 문자열을 반환합니다.

 

4-4가 좀 헷갈렸는데, 나는 이것을 uList.reverse로 해서 풀었다가 틀려서 찾아보니, 단순히 그냥 순서를 뒤집는게 아니라 ( 면 )로 바꾸고 ) 면 (로 바꾸라는 소리였다. 그래서 이 동작을 위해 아래와 같이 짧은 changeTag라는 함수를 작성했다.

function changeTag(n) {
  let string = '';

  for (let i = 0; i < n.length; i++) {
    if (n[i] === '(') {
      string += ')'
    } else {
      string += '('
    }
  }
  return string
}

 

코드가 좀 장황하지만 내 힘으로 풀 수 있어서 뿌듯하다.