Python에서 일치하는 패턴을 굵게 표시하는 프로그램 구현하기

문제 설명

텍스트와 문자열 리스트 patterns가 주어졌을 때, 텍스트에서 주어진 패턴 중 하나라도 일치하는 모든 부분 문자열을 와 태그로 감싸는 함수를 정의해야 합니다. 만약 두 패턴이 서로 인접하거나 겹쳐 있다면, 하나의 태그로 병합해야 합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

text = "thisissampleline"
patterns = ["this", "ssam", "sample"]

여기서 "this"는 인덱스 0~3에 위치하고, "ssam"과 "sample"은 인덱스 4부터 시작하여 서로 겹칩니다. 따라서 기대되는 출력 결과는 다음과 같습니다.

<b>this</b>i<b>ssample</b>line

해결 접근 방법

이 문제는 다음 단계를 거쳐 해결할 수 있습니다.

n := 텍스트의 길이
bold := 크기가 n인 리스트를 만들고 False 값으로 초기화
i를 0부터 n-1까지 반복하며 다음을 수행합니다.
- 각 패턴 p에 대해 text[i:]가 p로 시작하는지 확인하고, 시작한다면 j를 0부터 len(p)-1까지 반복하면서 bold[i + j] := True로 설정합니다.
ans := 빈 문자열
i를 0부터 n-1까지 반복하며 다음을 수행합니다.
- bold[i]가 True이고 (i == 0 또는 bold[i - 1]이 False)라면 ans에 ""를 연결합니다.
- ans에 text[i]를 연결합니다.
- bold[i]가 True이고 (i == n - 1 또는 bold[i + 1]이 False)라면 ans에 ""를 연결합니다.
ans를 반환합니다.

예제 코드

아래 구현 예시를 통해 더 자세히 이해할 수 있습니다.

class Solution:
    def solve(self, text, patterns):
        n = len(text)
        bold = [False] * n
        for i in range(n):
            for p in patterns:
                if text[i:].startswith(p):
                    for j in range(len(p)):
                        bold[i + j] = True

        ans = ""
        for i in range(n):
            if bold[i] and (i == 0 or not bold[i - 1]):
                ans += "<b>"
            ans += text[i]
            if bold[i] and (i == n - 1 or not bold[i + 1]):
                ans += "</b>"
        return ans

ob = Solution()
text = "thisissampleline"
patterns = ["this", "ssam", "sample"]
print(ob.solve(text, patterns))

입력

"thisissampleline", ["this", "ssam", "sample"]

출력

<b>this</b>i<b>ssample</b>line

동작 원리

첫 번째 이중 루프에서는 텍스트의 각 위치에서 시작하는 부분 문자열이 패턴 목록의 어떤 항목과 일치하는지 확인합니다. 일치하는 경우 해당 구간에 해당하는 bold 배열의 값을 True로 표시합니다. 두 번째 루프에서는 bold 배열을 처음부터 끝까지 순회하면서, 굵게 표시된 구간이 시작되는 지점에 태그를, 끝나는 지점에 태그를 삽입합니다. 이러한 방식 덕분에 인접하거나 겹치는 여러 패턴이 자동으로 하나의 태그로 병합됩니다.