Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열에 볼드() 태그 추가하는 방법

문제 개요

문자열 s와 문자열 목록 dict가 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 s 안에서 dict에 포함된 부분 문자열을 찾아, 여는 태그 <b>와 닫는 태그 </b> 한 쌍으로 감싸는 것입니다.

이때 두 가지 규칙을 반드시 지켜야 합니다.

  • 두 부분 문자열이 서로 겹쳐서(overlap) 나타나는 경우, 태그를 따로 감싸지 않고 한 쌍의 볼드 태그로 함께 감싸야 합니다.
  • 볼드 처리된 두 부분 문자열이 연속적으로 붙어 있는 경우, 이 역시 하나로 결합하여 한 번만 감싸야 합니다.

예를 들어 입력이 s = "abcxyz123"이고 dict = ["abc", "123"]라면, 출력 결과는 다음과 같습니다.

<b>abc</b>xyz<b>123</b>

풀이 접근 방법

이 문제는 각 위치가 볼드 처리 대상인지 먼저 표시한 뒤, 표시된 구간을 하나로 묶어 태그를 삽입하는 방식으로 해결할 수 있습니다. 알고리즘은 다음 단계로 진행됩니다.

  1. n을 문자열 s의 길이로 설정합니다.
  2. 크기가 n인 불리언 배열 bold를 선언합니다. 이 배열은 각 인덱스가 볼드 처리 대상인지를 나타냅니다.
  3. 결과를 저장할 빈 문자열 ret을 준비합니다.
  4. 인덱스 i를 0부터 s의 길이까지 순회하면서, 동시에 종료 지점 end를 0으로 초기화합니다.
    • 내부 반복문으로 j를 0부터 dict의 크기까지 순회합니다.
    • s의 인덱스 i부터 시작하는 부분 문자열이 dict[j]와 일치하는지 검사합니다.
    • 일치한다면 end를 end와 i + dict[j]의 길이 중 더 큰 값으로 갱신합니다.
  5. 각 위치에 대해 bold[i] = (end > i)로 설정합니다. 즉, 현재 위치가 어떤 사전 단어의 범위 안에 속하는지 판별합니다.
  6. 다시 i를 순회하면서 결과 문자열을 구성합니다.
    • bold[i]가 거짓이면 해당 문자를 그대로 ret에 추가하고 다음으로 넘어갑니다.
    • bold[i]가 참이면, 연속해서 볼드 구간인 지점까지 j를 전진시킵니다.
    • 구간 [i, j)를 찾았으므로 <b>와 </b> 사이에 해당 부분 문자열을 넣어 ret에 덧붙입니다. 이 과정에서 겹치거나 연속된 구간은 자연스럽게 하나의 태그로 묶입니다.
  7. 모든 순회가 끝나면 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string addBoldTag(string s, vector<string>& dict) {
      int n = s.size();
      vector<int> bold(n);
      string ret = "";
      for (int i = 0, end = 0; i < s.size(); i++) {
         for (int j = 0; j < dict.size(); j++) {
            if (s.substr(i, dict[j].size()) == dict[j]) {
               end = max(end, i + (int)dict[j].size());
            }
         }
         bold[i] = end > i;
      }
      int j;
      for (int i = 0; i < s.size(); i = j) {
         if (!bold[i]) {
            ret += s[i];
            j = i + 1;
            continue;
         }
         j = i;
         while (j < s.size() && bold[j])
         j++;
         ret += "<b>" + s.substr(i, j - i) + "</b>";
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"abc","123"};
   cout << (ob.addBoldTag("abcxyz123", v));
}

입력

"abcxyz123", ["abc","123"]

출력

<b>abc</b>xyz<b>123</b>

정리

이 알고리즘의 핵심은 두 단계로 나눌 수 있습니다. 첫째, 모든 사전 단어와 비교하여 각 인덱스가 볼드 구간에 포함되는지 미리 계산합니다. 둘째, 볼드 구간이 시작되는 지점에서 끝나는 지점까지 한 번에 묶어 태그를 삽입합니다. 이 방식을 사용하면 겹치는 구간이나 연속된 구간도 자동으로 하나의 태그로 병합되므로, 문제의 요구 조건을 깔끔하게 만족할 수 있습니다.