문자열이 오직 두 종류의 문자, 즉 "("와 ")"로만 구성되어 있다고 가정해 봅시다. 우리는 이러한 문자열을 입력받아, 필요한 만큼 "(" 또는 ")"를 삽입해 괄호의 균형을 맞추는 함수를 작성해야 합니다. 그리고 함수는 균형을 맞추기 위해 삽입한 문자의 최소 개수를 반환해야 합니다.
문제 예시
예를 들어, 다음과 같은 문자열이 주어졌다고 가정해 보겠습니다.
const str = '()))';
이 경우 출력값은 2가 되어야 합니다. 문자열 앞에 '(('를 추가하면 '((()))'가 되어 모든 괄호의 짝이 맞기 때문입니다.
해결 접근법: 스택(Stack) 활용
이 문제는 스택 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 여는 괄호 '('를 만나면 배열(스택)에 추가(push)합니다.
- 닫는 괄호 ')'를 만나면 배열의 마지막 요소를 확인합니다.
- 마지막 요소가 '('라면 짝이 맞으므로 제거(pop)하고, 그렇지 않다면 '#' 같은 표식을 추가해 보완이 필요함을 기록합니다.
- 모든 문자를 순회한 뒤 배열에 남아 있는 요소의 개수가 곧 필요한 최소 삽입 횟수입니다.
구현 코드
const str = '()))';
const balanceParanthesis = str => {
let paren = [];
for (let i = 0; i < str.length; i++) {
if (str[i] === "(") {
paren.push(str[i]);
} else if (str[i] === ")") {
if (paren[paren.length - 1] === "("){
paren.pop();
}else {
paren.push("#");
};
};
}
return paren.length;
}
console.log(balanceParanthesis(str));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
2
동작 원리 정리
- '('를 만나면 배열에 push하여 아직 짝을 찾지 못한 여는 괄호로 표시합니다.
- ')'를 만나면 배열의 마지막 요소를 검사합니다.
- 마지막 요소가 '('라면 서로 짝이 맞으므로 pop으로 제거합니다.
- 배열이 비어 있거나 짝이 맞지 않으면 '#'을 push하여 닫는 괄호가 부족한 상황을 기록합니다.
- 순회가 끝난 후 배열에 남은 요소 수('('와 '#')가 바로 균형을 맞추기 위해 삽입해야 할 최소 문자 수입니다.
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 공간 역시 최악의 경우 O(n)입니다. 따라서 길이가 긴 입력 문자열에서도 안정적으로 동작합니다.