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

파이썬으로 겹치지 않는 부분 문자열의 최대 개수 찾기

문제 소개

소문자로만 이루어진 문자열 s가 주어졌을 때, 아래 두 조건을 동시에 만족하는 비어 있지 않은 부분 문자열의 최대 개수를 구하는 프로그램을 만들어 보겠습니다.

  • 선택한 부분 문자열들은 서로 겹치지 않아야 합니다.
  • 어떤 부분 문자열에 특정 문자 ch가 포함되어 있다면, 원본 문자열에서 ch가 나타나는 모든 위치가 그 부분 문자열 범위 안에 포함되어야 합니다.

조건을 만족하는 부분 문자열의 개수를 최대화해야 하며, 같은 개수를 만족하는 해답이 여러 개라면 그중 총 길이가 가장 짧은 해답을 반환해야 합니다.

예시 확인

입력이 s = "pqstpqqprrr"인 경우를 살펴보겠습니다. 조건을 만족할 수 있는 후보 부분 문자열은 ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]이고, 이 가운데 개수를 최대로 하면서 총 길이가 최소가 되는 선택은 ["s", "t", "rrr"]입니다. 따라서 출력은 ['s', 't', 'rrr']이 됩니다.

알고리즘 접근 방법

핵심 아이디어는 각 고유 문자에 대해 첫 등장 위치(left)와 마지막 등장 위치(right)를 기준으로 필수 구간을 정의하고, 서로 엮여 있는 구간들을 집합 연산으로 병합한 뒤, 겹치지 않는 구간만 그리디하게 선택하는 것입니다. 단계별로 정리하면 다음과 같습니다.

  1. right 계산: 문자열 s에 등장하는 각 고유 문자 ch에 대해 오른쪽부터 탐색한 인덱스(rindex)를 모아 오름차순으로 정렬한 리스트를 만듭니다.
  2. left 계산: right의 각 인덱스 i에 해당하는 문자 s[i]가 처음 등장하는 위치(index)의 리스트를 만듭니다.
  3. 초기화: has와 gen을 빈 리스트로 준비합니다.
  4. i를 0부터 len(right) - 1까지 반복하면서:
    • gen의 끝에 s[right[i]] 한 글자로 이루어진 집합을 추가합니다.
    • has의 끝에 s[left[i] + 1 : right[i]] 구간(첫 등장과 마지막 등장 사이)의 문자 집합에서 gen의 마지막 항목을 뺀 집합을 추가합니다.
    • j를 len(has) - 2부터 0까지 감소시키며 반복합니다.
      • (has의 마지막 항목 ∩ gen[j])와 (has[j] ∩ gen의 마지막 항목)이 모두 공집합이 아니라면, 두 구간이 서로 의존 관계에 있으므로 다음과 같이 병합합니다.
        • gen의 마지막 항목 := gen의 마지막 항목 ∪ gen[j]
        • has의 마지막 항목 := (has의 마지막 항목 ∪ has[j]) − gen의 마지막 항목
        • has[j]와 gen[j]를 삭제합니다.
  5. 결과 조립 준비: res는 빈 리스트로, p_right는 -1로 초기화합니다.
  6. ind를 0부터 len(has) - 1까지 반복하면서:
    • l := left 값들 중 s[i]가 gen[ind]에 속하는 i들의 최솟값
    • r := right 값들 중 s[i]가 gen[ind]에 속하는 i들의 최댓값
    • p_right < l이면(이전에 선택한 구간과 겹치지 않으면):
      • res의 끝에 s[l : r + 1] 부분 문자열을 추가합니다.
      • p_right := r로 갱신합니다.
  7. res를 반환합니다.

파이썬 구현 코드

아래 예제 코드를 통해 전체 로직을 확인할 수 있습니다.

def solve(s):
    right = sorted([s.rindex(ch) for ch in set(s)])
    left = [s.index(s[i]) for i in right]

    has, gen = [], []
    for i in range(len(right)):
        gen.append(set(s[right[i]]))
        has.append(set(s[left[i] + 1:right[i]]) - gen[-1])

    for j in range(len(has) - 2, -1, -1):
        if (has[-1] & gen[j]) and (has[j] & gen[-1]):
            gen[-1] = gen[-1] | gen[j]
            has[-1] = (has[-1] | has[j]) - gen[-1]
            del has[j], gen[j]

    res, p_right = [], -1
    for ind in range(len(has)):
        l = min([i for i in left if s[i] in gen[ind]])
        r = max([i for i in right if s[i] in gen[ind]])
        if p_right < l:
            res.append(s[l : r + 1])
            p_right = r

    return res

s = "pqstpqqprrr"
print(solve(s))

입력

"pqstpqqprrr"

출력

['s', 't', 'rrr']

동작 원리 정리

이 알고리즘은 먼저 각 문자가 반드시 포함해야 하는 최소 범위, 즉 첫 등장 위치부터 마지막 등장 위치까지의 구간을 파악합니다. 어떤 구간 사이에 다른 문자가 끼어 있어 두 구간을 독립적으로 선택할 수 없는 경우에는 집합의 교집합과 합집합 연산을 통해 구간을 하나로 묶습니다. 병합이 끝난 뒤에는 왼쪽에서 오른쪽으로 훑으며, 이전에 선택한 구간의 끝(p_right)보다 시작점이 뒤에 있는 구간만 결과에 추가합니다. 이렇게 하면 겹침 없이 최대 개수의 부분 문자열을 얻을 수 있습니다.