괄호 변환

1. 개요

프로그래머스
Lv.2
2020 KAKAO BLIND RECRUITMENT
문제 바로가기

2. 문제 설명

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.

수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

2-1. 문제 설명 - 용어의 정의

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.

그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.

예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다.

반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.

'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
- 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
- 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
- 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
- 4-3. ')'를 다시 붙입니다.
- 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
- 4-5. 생성된 문자열을 반환합니다.

"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

2-2. 문제 설명 - 매개변수 설명

p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

2-3. 문제 설명 - 입출력 예

result

"(()())()"

")("

"()"

"()))((()"

"()(())()"

2-4. 문제 설명 - 입출력 예에 대한 설명

입출력 예 #1

이미 "올바른 괄호 문자열" 입니다.

입출력 예 #2

두 문자열 u, v로 분리합니다.
- u = ")("
- v = ""
u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다. -따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.

입출력 예 #3

두 문자열 u, v로 분리합니다.
- u = "()"
- v = "))((()"
문자열 u가 "올바른 괄호 문자열"이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
다시 두 문자열 u, v로 분리합니다.
- u = "))(("
- v = "()"
u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
- 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.

3. 문제 풀이

// 1) 올바른 괄호 문자열인지 확인하기
function is_correct(string) {
  let count = 0;
  for (let i = 0; i < string.length; i++) {
    if (string[i] === "(") {
      count++;
    } else if (count === 0) {
      return false;
    } else {
      count--;
    }
  }
  return true;
}

function solution(p) {
  // 2) 재귀함수 separate
  function separate(s) {
    // 3) count, u, v 선언하기
    let count = 0;
    let u, v;
    // 4) 매개변수로 받은 문자열의 길이 만큼 반복문 실행하기
    for (let i = 0; i < s.length; i++) {
      // 5) 반복문의 마지막이라면 매개변수로 받은 문자열과 ""로 나누기
      if (i === s.length - 1) {
        // 6) 매개변수로 받은 문자열이 올바른 괄호라면 해당 문자열을 반환하기
        if (is_correct(s)) {
          return s;
        } else {
          // 7) 매개변수로 받은 문자열이 올바른 괄호가 아니라면 올바른 괄호 만들기 과정 실행하기
          return (
            "(" +
            ")" +
            s
              .substr(1, i - 1)
              .split("")
              .map((item) => {
                if (item === "(") return ")";
                return "(";
              })
              .join("")
          );
        }
      }
      // 8) 첫 번재 반복이 아니고 count가 0이라면 매개변수로 받은 문자열을 두 개로 나눈후 반복문 종료하기
      if (i !== 0 && count === 0) {
        // 9) u에 매개변수로 받은 문자열를 인덱스 0부터 길이 i만큼 잘라 할당하기
        u = s.substr(0, i);
        // 10) v에 매개변수로 받은 문자열을 인덱스 i부터 마지막까지 잘라 할당하기
        v = s.substr(i);
        break;
      }
      // 11) 매개변수로 받은 문자열의 인덱스 i의 값에 따라 count 증가 또는 감소 시키기
      if (s[i] === "(") {
        count++;
      } else {
        count--;
      }
    }

    // 12) 문자열 u가 올바른 괄호라면 문자열 u와 separate(v)가 반환하는 문자열을 더해 반환하기
    if (is_correct(u)) {
      return u + separate(v);
    } else {
      // 13) 문자열 u가 올바른 괄호가 아니라면 올바른 괄호 만들기 과정 실행하여 만들어진 문자열을 반환하기
      return (
        "(" +
        separate(v) +
        ")" +
        u
          .substr(1, u.length - 2)
          .split("")
          .map((item) => {
            if (item === "(") return ")";
            return "(";
          })
          .join("")
      );
    }
  }

  return separate(p);
}

1) 올바른 괄호 문자열인지 확인하기

function is_correct(string) {
  let count = 0;
  for (let i = 0; i < string.length; i++) {
    if (string[i] === "(") {
      count++;
    } else if (count === 0) {
      return false;
    } else {
      count--;
    }
  }
  return true;
}

여는 괄호 또는 닫는 괄호로 이루어진 문자열이 올바른 괄호인지 확인하는 함수이다. "("이라면 count를 1증가시키고 ")"이라면 "count"를 1감소시킨다. count가 음수가 된다면 해당 문자열은 올바른 괄호가 아니므로 ")"가 반복문에 들어왔을 때 count가 0이라면 count를 1감소시켜 -1이 되기 때문에 false를 반환한다.

2) 재귀함수 separate

function separate(s) {}

separate 함수는 문자열을 매개변수로 받아 새로운 문자열을 반환하는 함수이다. 또한 이 함수는 리턴을 할 때 자기 자신을 다시 실행하기 때문에 재귀함수이다.

3) count, u, v 선언하기

let count = 0;
let u, v;

count: 균형잡힌 괄호 문자열을 만들기 위해 사용된다.
u: 균형잡힌 괄호 문자열이 처음으로 만들어지면 해당 변수에 할당한다.
v: u에 할당한 문자열을 제외한 나머지 문자열이다.

u와 v는 모두 균형잡힌 괄호 문자열이며 두 문자열은 separate 함수에 매개변수로 전해진 문자열을 바탕으로 만들어진다. u는 더 이상 균형잡힌 괄호 문자열로 나누어질 수 없지만 v는 균형잡힌 괄호 문자열로 또 나누어질 수 있고 빈 문자열이 될 수도 있다.

문제 설명을 참고하면 이해가 쉽다.

4) 매개변수로 받은 문자열의 길이 만큼 반복문 실행하기

for (let i = 0; i < s.length; i++) {}

separate 함수에 매개변수로 전달받은 문자열의 길이 만큼 반복문을 실행한다. 이 반복문에서는 u와 v에 새로운 문자열이 할당이 되거나 호출된 separate 함수를 종료시킨다.

5) 반복문의 마지막이라면 매개변수로 받은 문자열과 ""로 나누기

if (i === s.length - 1) {
}

만약 마지막 반복문까지 실행이 되었으면 u와 v를 따로 만들지 않고 매개변수로 받은 문자열 s로 조건문이 실행이 된다.

이때 u와 v로 따로 나누지 않은 이유는 매개변수로 받은 문자열이 두 개의 균형잡힌 괄호로 나누어지지 않기 때문이다. 매개변수로 받은 문자열이 하나의 균형잡힌 괄호이며 더 이상 나누어지지 않는다.

해당 부분은 리팩토링을 통해 바꾸어 보려고 한다. u를 매개변수로 받은 문자열, v를 빈 문자열로 할당할 계획이다.

6) 매개변수로 받은 문자열이 올바른 괄호라면 해당 문자열을 반환하기

if (is_correct(s)) {
  return s;
}

매개변수로 받은 문자열이 올바른 괄호라면 해당 문자열을 반환하고 함수를 종료한다.

7) 매개변수로 받은 문자열이 올바른 괄호가 아니라면 올바른 괄호 만들기 과정 실행하기

{
  return (
    "(" +
    ")" +
    s
      .substr(1, i - 1)
      .split("")
      .map((item) => {
        if (item === "(") return ")";
        return "(";
      })
      .join("")
  );
}

만약 매개변로 받은 문자열이 올바른 괄호가 아니라면 새로운 형태의 문자열을 반환해야한다.

"("와 ")"를 붙이고 매개변수로 받은 문자열의 맨 앞과 맨 뒤 괄호를 제거한 뒤 모든 괄호의 방향을 뒤집는다. 괄호의 방향을 뒤집는다는 것은 여는 괄호라면 닫는 괄호로 바꾸고 닫는 괄호라면 여는 괄호로 바꾼다는 것이다.

8) 첫 번재 반복이 아니고 count가 0이라면 매개변수로 받은 문자열을 두 개로 나눈후 반복문 종료하기

if (i !== 0 && count === 0) {
}

첫 번째 반복문일 때는 당연히 count의 값은 0이다. 그렇기 때무에 첫 번째 반복문은 제외하면서 count가 0일 때 매개변수로 받은 문자열을 두 개로 나누어야 한다.

또한 문자열을 두 개로 나누면 반복문을 종료한다.

9) u에 매개변수로 받은 문자열를 인덱스 0부터 길이 i만큼 잘라 할당하기

u = s.substr(0, i);

count가 증가 감소를 하는 도중 count이 되는 i의 값은 반드시 홀수이다. 하지만 count가 0이 되는 즉시 String.substr() 메서드를 사용하여 문자열을 자르는 것이 아니라 그 다음 반복문에서 String.substr() 메서드를 사용하여 문자열을 자르게 된다.

이렇게 코드를 작성한 이유는 균형잡힌 괄호가 되기 위해서는 기본적으로 문자열의 길이가 짝수이어야 하기 때문이다. i번째에서 count가 0이 되었다면 그 다음 반복문에서 i는 짝수이다. String.substr() 메서드의 두 번째 인수는 자르게 될 문자의 개수이다. 만약 생략될 경우 마지막 인덱스까지 자르게 된다.

물론 이렇게 하지 않고 count가 0이 되는 즉시 문자열을 자를 수도 있다. 이 방법에 대해서는 리팩토링을 통해 구현해보고자 한다.

10) v에 매개변수로 받은 문자열을 인덱스 i부터 마지막까지 잘라 할당하기

v = s.substr(i);

v에는 인덱스가 i인 부분부터 끝까지 잘라 새로운 문자열을 할당한다.

11) 매개변수로 받은 문자열의 인덱스 i의 값에 따라 count 증가 또는 감소 시키기

if (s[i] === "(") {
  count++;
} else {
  count--;
}

문자열의 인덱스가 i인 값이 "("라면 count를 1증가시키고 ")"라면 1감소시킨다.

count는 첫 반복문에서 음수 또는 양수의 값으로 시작한다.
count가 음수의 값이 될 수 있는 이유는 올바른 괄호가 아닌 균형잡힌 괄호로 나누는 과정이기 때문이다.
count가 음수로 시작하면 양수가 될 수 없고 양수로 시작하면 음수가 될 수 없다.
count가 0이 된다는 것은 처음부터 해당 인덱스까지가 하나의 균형잡힌 괄호라는 뜻이다.

12) 문자열 u가 올바른 괄호라면 문자열 u와 separate(v)가 반환하는 문자열을 더해 반환하기

if (is_correct(u)) {
  return u + separate(v);
}

문자열 u가 올바른 괄호라면 u에 separate(v) 함수를 실행하여 반환되는 문자열을 더해 만들어진 문자열을 반환한다.

해당 과정에서 현재 실행되고 있는 함수(separate)를 다시 호출하기 때문에 separate는 재귀함수이다.

13) 문자열 u가 올바른 괄호가 아니라면 올바른 괄호 만들기 과정 실행하여 만들어진 문자열을 반환하기

{
  return (
    "(" +
    separate(v) +
    ")" +
    u
      .substr(1, u.length - 2)
      .split("")
      .map((item) => {
        if (item === "(") return ")";
        return "(";
      })
      .join("")
  );
}

문자열 u가 올바른 괄호가 아니라면 올바른 괄호 만들기 과정을 실행한다. 실행되어 만들어진 문자열을 반환한다.

해당 과정에서도 현재 실행중인 separate 함수가 호출된다.

결과

4. Refactoring

function is_correct(string) {
  let count = 0;
  for (let i = 0; i < string.length; i++) {
    if (string[i] === "(") {
      count++;
    } else if (count === 0) {
      return false;
    } else {
      count--;
    }
  }
  return true;
}

// 1) 올바른 괄호로 만드는 함수
function make_correct(string) {
  return string
    .substr(1, string.length - 2)
    .split("")
    .map((item) => {
      if (item === "(") return ")";
      return "(";
    })
    .join("");
}

function solution(p) {
  function separate(s) {
    let count = 0;
    let u, v;
    for (let i = 0; i < s.length; i++) {
      if (s[i] === "(") {
        count++;
      } else {
        count--;
      }

      // 2) count가 0이 될 때 변수 u와 변수 v에 새로운 문자열 할당하기
      if (count === 0) {
        u = s.substr(0, i + 1);
        v = s.substr(i + 1);
        break;
      }
    }

    // 3) v가 빈문자열일 때와 아닐 때를 구분하기
    v = v === "" ? v : separate(v);
    if (is_correct(u)) {
      return u + v;
    } else {
      return "(" + v + ")" + make_correct(u);
    }
  }
  return separate(p);
}

리팩토링을 한 부분을 위주로 살펴본다.

1) 올바른 괄호로 만드는 함수

function make_correct(string) {
  return string
    .substr(1, string.length - 2)
    .split("")
    .map((item) => {
      if (item === "(") return ")";
      return "(";
    })
    .join("");
}

올바른 괄호로 만드는 과정을 함수로 만들어 필요한 부분에 호출하도록 하였다.

2) count가 0이 될 때 변수 u와 변수 v에 새로운 문자열 할당하기

if (count === 0) {
  u = s.substr(0, i + 1);
  v = s.substr(i + 1);
  break;
}

반복문에서 count가 0일 될 때 실행된다. 문자열의 처음 인덱스부터 i의 값에 1을 더한 수 만큼 잘라 u에 할당하고 나머지 문자열은 v에 할당한다.

이때 u는 반드시 균형잡힌 문자열이며 v는 균형잡힌 문자열 또는 빈 문자열이다.

3) v가 빈문자열일 때와 아닐 때를 구분하기

v = v === "" ? v : separate(v);

만약 v가 빈 문자열이면 자기 자신의 값을 그대로 가지지만 빈 문자열이 아니라면 separate(v) 함수를 호출하여 반환되는 문자열을 할당한다.

결과

리팩토링을 통해 실행속도가 조금 빨라졌다. 또한 가독성도 나름 좋아진 듯 하다.

5. Conclusion

프로그래머스 기준 레벨2의 문제이다. 내가 너무 레벨2에 대해 어렵게 생각하는 건지 모르겠지만 문제를 이해하는 것 조차 힘들었다. 특히 올바른 괄호를 만드는 과정을 글로 읽어도 이해가 잘 되지 않았다. 생각해보면 소개한 절차대로만 코드를 작성을 하면 되는 것이었는데 너무 어렵게 생각을 한 것이 아닐까 싶다... 너무 어렵게 접근하지 말자. 처음 이해가 잘 안되면 그림이라도 그려서 이해를 하도록 하자. 문제의 이해부터 얼른 해야 시간을 아끼면서 풀 수 있을 듯 하다. 재귀 함수에 대해 나는 지금까지 어렵고 복잡한 그래서 구현하기 힘든 것이라고 생각해왔다. 이번 문제는 그런 재귀 함수를 이용하여 푸는 문제였다. 그래서 더 겁을 먹은 것이지 않을까 싶은 생각이 든다. 하지만 재귀 함수도 누구나 구현 가능한 함수이기 때문에 나도 구현을 할 수 있다. 내가 작성한 재귀 함수도 잘 실행이 되니 조금은 자신감을 가져도 되지 않을까?

📅 2022-09-04

Previous올바른 괄호 Next프린터

Last updated 2 years ago