문자열이 오직 두 종류의 문자, 즉 '('와 ')'로만 구성되어 있다고 가정해 봅시다. 이때 우리는 이러한 문자열을 입력받아 필요한 만큼 '(' 또는 ')'를 삽입하여 괄호의 균형을 맞추는 함수를 작성해야 합니다.
그리고 이 함수는 균형을 맞추기 위해 문자열에 삽입한 문자의 최소 개수를 반환해야 합니다.
예를 들어, 문자열이 다음과 같다면 −
const str = '()))';
출력 결과는 2가 되어야 합니다. 문자열 앞에 '(('를 추가하면 괄호의 균형이 맞춰지기 때문입니다.
접근 방식: 스택(Stack) 활용
이 문제는 스택 자료구조를 활용하면 간단하게 해결할 수 있습니다. 동작 원리는 다음과 같습니다.
1. 여는 괄호 처리
문자열을 순회하면서 '('를 만나면 스택에 push합니다. 이는 아직 짝을 찾지 못한 여는 괄호라는 의미입니다.
2. 닫는 괄호 처리
')'를 만나면 스택의 마지막 요소를 확인합니다. 마지막 요소가 '('라면 서로 짝이 맞으므로 pop하여 제거하고, 그렇지 않다면 짝이 없는 닫는 괄호이므로 대체 문자 '#'를 push합니다.
3. 결과 계산
모든 순회가 끝난 후 스택에 남아 있는 요소의 개수가 곧 균형을 맞추기 위해 필요한 최소 삽입 횟수입니다. 남은 '('는 앞에 추가해야 할 ')'의 수를, '#'는 추가해야 할 '('의 수를 의미합니다.
예제 코드
다음은 위 로직을 구현한 전체 코드입니다 −
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
동작 과정 살펴보기
입력 문자열 '()))'에 대해 코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.
- 인덱스 0: '('를 만나므로 스택에 push → 스택: ['(']
- 인덱스 1: ')'를 만나고, 스택 마지막 요소가 '('이므로 pop → 스택: []
- 인덱스 2: ')'를 만나지만 스택이 비어 있으므로 '#'를 push → 스택: ['#']
- 인덱스 3: ')'를 만나지만 스택 마지막 요소가 '#'이므로 '#'를 push → 스택: ['#', '#']
최종적으로 스택에는 2개의 요소가 남아 있으며, 이는 앞에 '((' 두 개를 삽입하면 균형이 맞춰진다는 것을 의미합니다. 따라서 결과값은 2입니다.
시간 복잡도
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 공간 복잡도 역시 최악의 경우 모든 문자가 스택에 저장될 수 있어 O(n)입니다. 매우 효율적인 해결 방법이라 할 수 있습니다.