쓰여 있는 그대로 풀면 되는 문제
문제가 이해가 안되는 부분이 있었다.
괄호로 이루어진 주어진 문자열의 (
와 )
의 개수가 같다면, 균형잡힌 괄호
문자열입니다.
여기에, 짝이 맞도록 올바른 괄호라면 올바른 괄호
문자열 입니다.
균형잡힌 괄호 p
가 주어질 때, 다음 알고리즘에 따라 올바른 괄호
로 변환하고 반환합니다.
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. 생성된 문자열을 반환합니다.
여기에서 2번 항목이 잘 이해가지 않았다. ( 저 설명과, 예시가
u
와v
를 구분하는 데 유추할 수 있는 모든 정보지만 명확하지 않았다 )
문제 사이트의 커뮤니티를 활용한 결과
u
는 앞에서부터 분리할 수 있는 가장 작은 균형잡힌 괄호이고, v
는 그 외 괄호들이다.
예시 : ))(()(
u
: ))((
v
: )(
맨 앞부터 읽으면서, 처음 )
와 (
의 개수가 같아질 때, 그 만큼을 u
로 분리하면 된다.
재귀의 Base : 빈문자열 일 때, 빈문자열을 반환합니다.
u
와 v
를 분리하기 위해, balnace
에 (
라면 +1
, )
라면 -1
로 하여
처음 0
이 될 때(즉, 균형잡힌 괄호
)의, index
로 u
와 v
를 분리한다.
isCorrect
로 올바른 괄호
를 확인하고 문제에 주어진 대로 처리한다. (3번, 4번)
올바르다면 u
+ solution(v)
,
아니라면 새로운 문자열을 생성한다.
function solution(p) {
if(p == '') return '';
let balance = 0;
let index = 0;
do{
balance += p[index++] == '('?1:-1;
} while(balance != 0);
const u = p.slice(0,index);
const v = p.slice(index);
if (isCorrect(u)) {
return u + solution(v);
}
else {
return create(u,v);
}
}
올바른 괄호
확인은 stack
을 활용하여,
마지막 요소가 (
이고, 현재가 )
일 때 stack
에서 없앤다.
stack
에 요소가 남아있다면, 올바른 괄호
가 아니다.
function isCorrect(s) {
const stack = [];
for (const braket of s) {
if (stack[stack.length-1] == '(' && braket == ')') stack.pop();
else stack.push(braket);
}
return stack.length == 0;
}
새 문자열 생성은 문제에 주어진 대로 처리한다. (4-1번 ~ 4-2번)
function create(u,v) {
let result = '';
result += '(';
result += solution(v);
result += ')';
const inner = u.slice(1,-1);
for (const bracket of inner) {
result += bracket == '('? ')' : '(';
}
return result;
}