[python3] 2405. Optimal Partition of String

풀이 일자: 23.04.04

난이도: [Medium]

분류: [Hash Table, String, Greedy]

문제 내용

s라는 문자열이 주어졌을 때 이를 여러 개의 subString으로 자른다고 했을 때 각각의 subString 내의 중복되는 문자가 unique하게 자를 때 최소한으로 나오는 subString의 갯수를 리턴하라는 문제이다.

 

문제 해결 흐름

1. 일단 가장 간단하게 생각하면 앞에서부터 탐색하면서 카운팅하면 되겠네.

→ 앞에서부터 array에 문자를 넣기 시작하다가 array내부에 있는 문자가 나오면 ans+=1을 하고 거기서부터 다시 나온 문자에 대해 history를 저장하면 되겠다.

 

class Solution:
    def partitionString(self, s: str) -> int:
        case = list();
        ans = 0;
        
        for i in range(len(s)):
            if s[i] not in case:
                case.append(s[i]);
            else:
                ans += 1;
                case.clear();
                case.append(s[i])
        
        ans += 1;
        return ans;

=> Medium 문제가 이렇게 쉬울리 없어라는 생각으로 TLE가 나올 것으로 예상했으나 Pass가 된 code

 

Time Complexity:  O(26*N)

모든 문자열 내의 문자 순회 * case내부 순회로 총 N*26의 시간복잡도를 갖겠다.

 

Space Complexity: O(26)

case라는 배열에 들어올 수 있는 경우의 수가 a-z까지 모두 다 들어올 수 있기에 26의 Space Complexity를 갖겠다.

 

 

2. 배열을 통해서 있는지 여부를 계산하는 건 너무 기초적인 방법인 것 같아. 다른 방법이 없을까.

→ 위의 방법보다 빠른지는 모르겠지만 배열에 저장하지 말고 26진수로 생각해서 하나의 변수에 정보를 넣어서 비교해볼까?

 

class Solution:
    def partitionString(self, s: str) -> int:

        digit, hsh = 0,0;   # 현재 기억하려는 문자의 자릿수, 문자의 해시값
        ans = 0;

        for i in s:
            dgt, num = digit, hsh;
            sig = False;
            while(dgt != 0):
                lttr = num % 26;
                num = num // 26;
                if (chr(lttr + 97) == i):    # 26진수로 26으로 나눴을 때 나머지가 각 문자를 의미
                    sig = True;
                    break;
                dgt -= 1;
            
            if sig:							# 만약 같은게 있다면 ans를 증가시키고 거기서부터 다시 시작
                ans += 1;
                hsh = ord(i) - 97;
                digit = 1;
            else:							# 없다면 26진수에 맞게 26을 곱해주고 현재의 문제를 넣어준다.
                hsh *= 26;
                hsh += (ord(i) - 97);
                digit += 1;					# 만든 26진수의 자리수.

        ans += 1;
        
        return ans;

=> 이를 통해 수를 이용한 계산보다는 차라리 배열의 순회가 빠르다는 것을 알 수 있었다.

 

Time Complexity:  O(26*N)

모든 문자열 내의 문자 순회 * 해시값을 다시 풀어서 자릿수별로 계산으로 총 N*26의 시간복잡도를 갖겠다.

 

Space Complexity: O(1)

이전 풀이처럼 배열을 사용하지 않고 숫자로 지금까지의 문자정보를 저장했으므로 1의 공간복잡도를 가질 것이다.

 

다른 해결 방식

1. Official Solution에서는 Greedy 방식을 사용했다.

class Solution:
    def partitionString(self, s: str) -> int:
        lastSeen = [-1]*26       # 이전에 존재했다면 몇번째에 마지막으로 있었는지를 tracking
        count = 1
        substringStarting = 0    # substring의 시작점

        for i in range(len(s)):  # s를 순회해
            if lastSeen[ord(s[i]) - ord('a')] >= substringStarting:  # 이번에 들어온게 substring 시작점 이후에 본 적이 있으면
                count += 1											 # 여기서부터 다시 세
                substringStarting = i
            lastSeen[ord(s[i]) - ord('a')] = i						 # 해당 알파벳을 마지막으로 본 index로 지정을해

        return count

Time Complexity:  O(N)

s에 대한 순회만 하면 되기에 N의 시간복잡도를 갖는다.

 

Space Complexity: O(26)

해당 알파벳이 마지막으로 언제 등장했는지를 기록하기 위한 lastSeen이라는 배열을 사용하기에 O(26)의 공간복잡도를 가진다.

 

2. 그다음으로 많이 푼 방식이 Bit manipulation을 이용한 방식이다.

→ Official Solution에서 lastSeen대신 1과 0을 넣어 bit 연산자를 사용한 방식이다.

 

 

문제 링크

https://leetcode.com/problems/optimal-partition-of-string/description/

Optimal Partition of String - LeetCode