2405. Optimal Partition of String

abacaba

 

위와 같은 문자열이 입력으로 주어질 때, 이 문자열을 중복되는 문자가 없는 부분 문자열들로 쪼갤 때 초대한 적게 쪼개는 수를 반환하는 문제입니다. 

 

해결

이 문제는 사실, 문제의 본질을 이해하느냐 못하느냐를 파악하기 위한 문제 입니다. 

 

예를 들어, 입력으로 주어진 문자열을 서로 다른 여러 방식으로 쪼개는 것들을 모두 시도해 본 후 (brute-force) 이 중 가장 적은 수로 쪼개지는 경우를 찾고자 한다면, 다음과 같이 구현하면 됩니다. 

 

def partitionString(self, s: str) -> int:
    n = len(s)

    def dfs(start, cnt, trace):
        if start == n:
            return cnt
        
        if (start, cnt) in mem:
            return mem[(start, cnt)]
        
        aset = set()
        mn = float('inf')

        for i in range(start, n):
            if s[i] in aset:
                break

            aset.add(s[i])
            mn = min(mn, dfs(i + 1, cnt + 1, trace + [aset]))
        
        mem[(start, cnt)] = mn
        return mn
    
    mem = {}
    res = dfs(0, 0, [])
    return res

 

그러나 위의 코드는 timeout을 만나게 됩니다. 

그렇다면 다른 approach를 찾아야 한다는 것을 의미합니다. 

 

입력을 가만 살펴보니, 

abacaba를 중복이 없는 그러나 최대한 많은 문자를 포함하도록 문자로 쪼갤때, 다음과 같이 쪼갤 수 있습니다.

 

ab, ac, ab, a

a, ba, ca, ba

 

앞에서 진행하는 경우와 뒤에서 진행하는 두 가지 경우로 나눠 볼 수 있습니다. 

그런데 두 경우 모두 최대한 긴 substring을 만들면서 쪼개는 경우 부분문자열의 개수는 4개로 동일합니다. 

 

이제 간단하게 문자열의 앞에서부터 중복이 없는 부분문자열을 만들면 된다는 것을 알 수 있습니다. 

def partitionString(self, s: str) -> int:
    sub = ''
    cnt = 0

    for i in range(len(s)):
        if s[i] not in sub:
            sub += s[i]
        else:
            cnt += 1
            sub = s[i]

    return cnt + 1

 

Kotlin으로는 다음과 같이 구현 가능합니다. 

 

class Solution {
    fun partitionString(s: String): Int {
        var sub: String = ""
        var cnt: Int = 0

        for (i in 0 until s.length) {
            if (sub.contains(s[i])) {
                cnt += 1
                sub = ""
                sub += s[i]
            } else {
                sub += s[i]
            }
        }

        return cnt + 1
    }
}