문제
문제 정의
문자열에 포함된'('와 ')'의 개수가 같을 경우 이를 "균형잡힌 괄호 문자열" 이라고 한다.
균형잡힌 괄호 문자열의 '('와 ')'가 올바르게 짝지어져있다면 이를 "올바른 괄호 문자열" 이라고 한다.
예를 들어 ")()("는 균형잡힌 괄호 문자열은 맞지만 올바른 괄호 문자열은 아니다.
균형잡힌 괄호 문자열이 주어졌을 때, 올바른 괄호 문자열로 변환하여 출력해야 한다.
올바른 괄호 문자열로 변환하는 방법은 아래와 같다.
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. 입력이 빈 문자열인가? (아니오)
2. 문자열 u,v로 분리
u: () // 균형잡힌 문자열
v: ))((() // 나머지
3. 문자열 u가 "올바른 괄호 문자열"인가? (예)
1단계부터 다시 수행
입력: ))((() // v
1. 입력이 빈 문자열인가? (아니오)
2. 문자열 u,v로 분리
u: ))(( // 균형잡힌 문자열
v: () // 나머지
3.문자열 u가 "올바른 괄호 문자열"인가? (아니오)
4.문자열 u가 "올바른 괄호 문자열"이 아닌가? (예)
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
문자열: "("
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
입력: () // v
1. 입력이 빈 문자열인가? (아니오)
2. 문자열 u,v로 분리
u: () // 균형잡힌 문자열
v: '' // 나머지
문자열: "(()"
4-3. ')'를 다시 붙입니다.
문자열: "(())"
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
u: ))(( -> )( -> ()
문자열: (())()
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
u: ()
결과 문자열: (())()
u+결과 문자열: ()(())()따라서 답은 "()(())()" 가 되어야 한다.
해결방안
문제에서 나온 변환과정대로 코드를 구현했다.
코드 (통과)
function solution(p) {
let answer = makeCorrect(p);
function makeCorrect(w) {
if (w === '') return '';
let open = 0;
let close = 0;
let u = '';
for (let i = 0; i < w.length; i++) {
if (w[i] === '(') {
open++;
u += '(';
}
if (w[i] === ')') {
close++;
u += ')';
}
// 균형잡힌 괄호 문자열이라면 break
if (open === close) break;
}
let v = w.slice(u.length);
// u가 올바른 괄호 문자열이라면
if (checkCorrect(u)) {
u += makeCorrect(v);
return u;
} else {
let str = '(';
str += makeCorrect(v);
str += ')';
// u의 첫 번째, 마지막 문자 제거
u = u.replace(/^.|.$/g, '');
// 나머지 문자열 괄호 방향 뒤집기
for (let i = 0; i < u.length; i++) {
if (u[i] === '(') str += ')';
else str += '(';
}
return str;
}
}
return answer;
}
function checkCorrect(str) {
let open = 0;
let close = 0;
for (let i = 0; i < str.length; i++) {
if (str[i] === '(') open++;
if (str[i] === ')') close++;
// 닫는 괄호가 더 많아질 경우 false
if (close > open) return false;
}
// 여는 괄호와 닫는 괄호의 개수가 같다면 true
return open === close;
}통과는 했지만 더 나은 방법이 없을까 확인하기 위해 다른 분들의 코드를 보았고 이를 통해 코드를 개선시켰다.
코드 (개선)
일단 checkCorrect 함수를 따로 만들지 않아도 "올바른 괄호 문자열"인지 확인하는 방법이 있었다.
function solution(p) {
let answer = makeCorrect(p);
function makeCorrect(w) {
if (w === '') return '';
let open = 0;
let close = 0;
let u = '';
for (let i = 0; i < w.length; i++) {
if (w[i] === '(') {
open++;
u += '(';
}
if (w[i] === ')') {
close++;
u += ')';
}
if (open === close) break;
}
let v = w.slice(u.length);
if (u[0] === '(') { // 바뀐 부분
u += makeCorrect(v);
return u;
} else {
let str = '(';
str += makeCorrect(v);
str += ')';
// u의 첫 번째, 마지막 문자 제거
u = u.replace(/^.|.$/g, '');
// u의 나머지 문자열 괄호 방향 뒤집기
for (let i = 0; i < u.length; i++) {
if (u[i] === '(') str += ')';
else str += '(';
}
return str;
}
}
return answer;
}u가 "균형잡힌 괄호 문자열"일때, 맨 앞에 있는 괄호가 여는 괄호('(')라면 "올바른 괄호 문자열"일 수밖에 없다는 점을 이용했다.
코드 (리팩터링)
function solution(p) {
let answer = makeCorrect(p);
function makeCorrect(w) {
...
// u가 올바른 괄호 문자열이라면
if (u[0] === '(') {
u += makeCorrect(v);
return u;
} else {
// 앞 뒤 괄호 추가
let str = '(' + makeCorrect(v) + ')';
// u의 첫 번째, 마지막 문자 제거하고 나머지 문자열 괄호 방향 뒤집기
u = u.slice(1,u.length-1).split('').map(e=>e==='(' ? ')' : '(').join("");
return str+u;
}
}
return answer;
}올바른 괄호 문자열이 아닐 때 처리해주는 부분의 코드를 정리했다.
코드 (리팩터링)
function solution(p) {
let answer = makeCorrect(p);
function makeCorrect(w) {
if (w === '') return '';
let sum = 0
let idx = 0;
do { sum += w[idx++] === '(' ? 1 : -1 } while(sum !== 0)
let u = w.slice(0,idx);
let v = w.slice(idx);
// u가 올바른 괄호 문자열이라면
if (u[0] === '(') {
u += makeCorrect(v);
return u;
} else {
// 앞 뒤 괄호 추가
let str = '(' + makeCorrect(v) + ')';
// u의 첫 번째, 마지막 문자 제거하고 나머지 문자열 괄호 방향 뒤집기
u = u.slice(1,u.length-1).split('').map(e=>e==='(' ? ')' : '(').join("");
return str+u;
}
}
return answer;
}"균형잡힌 괄호 문자열"을 만드는 부분을 수정했다.
인덱스가 1씩 증가하며, w[idx]가 '('라면 sum을 1 증가시키고 아니라면 sum을 1 감소시킨다.
따라서 sum 0이 된다면 여는 괄호의 개수와 닫는 괄호의 개수가 같은 것이므로 그때 while을 종료한다.
그리고 그때의 인덱스를 이용해서 w를 u와 v로 나눠준다.
코드 (리팩터링)
function solution(p) {
const reverse = (u) => u.slice(1,u.length-1).split('').map(e=>e==='(' ? ')' : '(').join("");
function makeCorrect(w) {
if (w === '') return '';
let sum = 0
let idx = 0;
do { sum += w[idx++] === '(' ? 1 : -1 } while(sum !== 0)
let u = w.slice(0,idx);
let v = makeCorrect(w.slice(idx));
if (u[0] === '(') return u+v;
else return '(' + v + ')' + reverse(u);
}
let answer = makeCorrect(p);
return answer;
}u가 올바른 괄호일 때든, 아닐 때든 makeCorrect(v)를 수행해줘야 하므로 처음에 w를 u와 v로 나눌때 아예 makeCorrect(v)를 수행해준다. 그리고 u의 앞 뒤 괄호를 제거하고 뒤집어주는 코드는 reverse함수로 따로 빼서 가독성을 높였다.
그럼 위와 같이 코드를 깔끔하게 정리할 수 있다.
지속적인 성장