Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

JavaScript로 꺾쇠괄호 문자열 균형 맞추기: 앞뒤에 괄호 추가하는 방법

문제 소개

꺾쇠괄호(<, >)로만 구성된 문자열이 주어졌을 때, 문자열의 맨 앞과 맨 뒤에 괄호를 추가하여 모든 괄호가 서로 짝을 이루도록 만드는 함수를 작성해야 합니다.

여기서 꺾쇠괄호가 올바르게 매칭되려면, 모든 <에 대응하는 >가 존재하고, 반대로 모든 >에도 대응하는 <가 존재해야 합니다.

입력 예시

const str = '><<><';

출력 결과

const output = '<><<><>>';

위 예제에서는 문자열의 균형을 맞추기 위해 앞에 < 한 개를, 뒤에 >> 두 개를 추가했습니다.

해결 접근 방식

이 문제는 간단한 카운터 변수 두 개만으로 효율적으로 해결할 수 있습니다.

  • count: 지금까지 등장했지만 아직 짝을 찾지 못한 열린 태그(<)의 개수를 추적합니다.
  • extras: 짝이 없는 닫힌 태그(>)의 개수를 세어, 나중에 문자열 앞에 추가할 <의 개수를 결정합니다.

문자열을 처음부터 끝까지 순회하면서 다음 규칙을 적용합니다.

  1. >를 만났을 때 count가 0이면, 짝이 없는 태그이므로 extras를 1 증가시킵니다.
  2. >를 만났을 때 count가 0보다 크면, 앞서 저장된 <와 짝을 이루므로 count를 1 감소시킵니다.
  3. <를 만나면 count를 1 증가시킵니다.
  4. 순회가 끝나면 extras만큼 <를 문자열 앞에, count만큼 >를 문자열 뒤에 붙여 최종 결과를 반환합니다.

구현 코드

const str = '><<><';

const buildPair = (str = '') => {
  let count = 0;
  let extras = 0;
  for (const char of str) {
    if (char === '>') {
      if (count === 0) {
        extras++;
      } else {
        count--;
      }
    } else {
      count++;
    }
  }
  const leadingTags = '<'.repeat(extras);
  const trailingTags = '>'.repeat(count);
  return leadingTags + str + trailingTags;
};

console.log(buildPair(str));

실행 결과

><<><>>

마무리

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 스택 같은 추가 자료구조 없이 숫자 카운터만 사용하기 때문에 공간 복잡도 역시 O(1)로 매우 효율적입니다. 괄호 균형 검사는 컴파일러의 구문 분석이나 HTML/XML 유효성 검사 등 다양한 분야에서 활용되는 기본 알고리즘이므로 잘 익혀두면 큰 도움이 됩니다.