add: 프로그래머스/괄호 변환

dididy · dididy · commit b272fa431577 · 2021-02-10T18:47:56.000+09:00
diff --git a/programmers/괄호 변환/README.md b/programmers/괄호 변환/README.md
@@ -0,0 +1,91 @@
+# [괄호 변환 / 60058](https://programmers.co.kr/learn/courses/30/lessons/60058?language=javascript)
+
+## What
+
+###### Description
+
+카카오에 신입 개발자로 입사한 **콘**은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.  
+수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
+
+### 용어의 정의
+
+**'('** 와 **')'** 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 **`균형잡힌 괄호 문자열`**이라고 부릅니다.  
+그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 **`올바른 괄호 문자열`**이라고 부릅니다.  
+예를 들어, `"(()))("`와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.  
+반면에 `"(())()"`와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.
+
+'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.
+
+    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. 생성된 문자열을 반환합니다.
+
+**균형잡힌 괄호 문자열** p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 **올바른 괄호 문자열**로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
+
+### 매개변수 설명
+
+- p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
+- 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
+- 만약 p가 이미 올바른 괄호 문자열이라면 그대로 return 하면 됩니다.
+
+---
+
+### 입출력 예
+
+<table class="table"><thead><tr><th>p</th><th>result</th></tr></thead><tbody><tr><td><code>"(()())()"</code></td><td><code>"(()())()"</code></td></tr><tr><td><code>")("</code></td><td><code>"()"</code></td></tr><tr><td><code>"()))((()"</code></td><td><code>"()(())()"</code></td></tr></tbody></table>
+
+### 입출력 예에 대한 설명
+
+**입출력 예 #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의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 `"()"`이 됩니다.
+  - 따라서 생성되는 문자열은 `"("` + `"()"` + `")"` + `"()"`이며, 최종적으로 `"(())()"`를 반환합니다.
+- 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 `"()"` + `"(())()"` = `"()(())()"`가 됩니다.
+
+---
+
+혼자 풀기가 막막하다면, 풀이 강의를 들어보세요 [(클릭)](https://programmers.co.kr/learn/courses/10336?utm_source=programmers&utm_medium=test_course10336&utm_campaign=course_10336)
+
+> 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/60058
+
+## How
+괄호나와서 당연히 스택 쓰는줄 알고 스택을 사용에 포커스를 두고 풀려고 했는데 괄호가 한가지 종류이기도 해서 꼭 스택을 써야 풀리는 문제는 아니었다. 조건을 하나씩 옮겨야 풀리는 구현문제였다. 균형잡힌 괄호 문자열일 경우 올바른 괄호문자열로 만드는 것이 문제의 목표이다. 문제에 주어진 input을 기반으로 생각해보면 다음과 같다.
+
+1. "(()))("는 균현잡힌 빈 문자열이지만 올바른 괄호문자열은 아니다. 따라서 두개의 균형잡힌 괄호 문자열 u, v로 분리가 가능하다.
+  - u인 "(())"는 가만히 두고 v인 ")("에 대해서 재귀적으로 solution 함수를 실행한다.
+  - 재귀호출된 상태에서 u는 ")(" v는 ""이 된다.
+2. u가 올바른 괄호 문자열이 아니므로 아래의과정을 수행한다.
+  - "(" 와 ")"을 각각 앞뒤로 붙이고 중간에 v에 해당하는 부분을 재귀적으로 solution 함수 실행한 결과를 추가하여 문자열을 반환한다.
+
+이런 과정을 거치게 되면 "(()))("가 "(())()"로 변화되어 반환됨을 알 수 있다. 즉 재귀적인 흐름으로 조건에 맞지 않는 부분을 조건에 맞도록 연쇄적으로 반환하도록 하면 된다. 이외에도 빈 문자열같은 예외처리 요구사항을 추가하면 문제를 해결할 수 있다.
+
+## Retrospective
diff --git a/programmers/괄호 변환/answer.test.js b/programmers/괄호 변환/answer.test.js
@@ -0,0 +1,50 @@
+function solution(p) {
+  let answer = '';
+  let openBracketCount = 0;
+  let closeBracketCount = 0;
+  let checkString = true;
+
+  if (p.length === 0) {
+    // 1
+    return answer;
+  }
+
+  for (let i = 0; i < p.length; i++) {
+    if (p[i] === '(') {
+      openBracketCount += 1;
+    }
+    if (p[i] === ')') {
+      closeBracketCount += 1;
+    }
+
+    if (openBracketCount < closeBracketCount) {
+      checkString = false;
+    }
+
+    if (openBracketCount === closeBracketCount) {
+      if (checkString === true) {
+        // 2, 3
+        answer += p.slice(0, i + 1) + solution(p.slice(i + 1));
+
+        return answer;
+      }
+
+      // 4-1,2,3
+      answer = '(' + solution(p.slice(i + 1)) + ')';
+
+      // 4-4
+      for (let j = 1; j < i; j++) {
+        answer += p[j] === '(' ? ')' : '(';
+      }
+
+      // 4-5
+      return answer;
+    }
+  }
+}
+
+test('Test case', () => {
+  expect(solution('(()())()')).toEqual('(()())()');
+  expect(solution(')(')).toEqual('()');
+  expect(solution('()))((()')).toEqual('()(())()');
+});
