[코테] 99클럽 코테 스터디 40일차 TIL - 그리디

Question1 - [미들러] 문자열의 최적 구분 (Optimal Partition of String)

 

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return the minimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

 

Example 1:

• Input: s = "abacaba"
• Output: 4

Explanation:

• Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
• It can be shown that 4 is the minimum number of substrings needed.

Constraints:

• 1 <= s.length <= 105
• s consists of only English lowercase letters.

---

 

문제풀이

 

그리디, 탐욕법으로 푸는 문제로, 각 단계에서 최선의 선택을 해야 함. 

그리디 문제는 보통 가장 빠르게 최적 해를 찾을 수 있는 원칙이 필요한데

이 문제에서는 문자열 s를 돌면서, 현재의 substring 리스트에 해당 문자를 중복없이 추가할 수 있는지 판단하고,

만약에 중복이 발생하면 새로운 substring을 생성하는 규칙이 필요하다.

 

trial1 

 

처음에는 아래 코드처럼 너무 단순하게 s의 알파벳들중 가장 많은 요소의 개수만큼 substring을 만들면 될것이라고 생각했는데, 

그렇게로는 모든 케이스를 pass하지 못했다. 

from collections import Counter

class Solution(object):
    def partitionString(self, s):
 		 
        count = Counter(s)
        count_list = count.values()

        return max(count_list)

 

최소의 substring의 개수가, 전체 문자열 s에서 가장 많이 중복된 개수와 항상 같지 않기 때문에 이 방법으로는 불충분하다.

왜냐하면 substring과 subsequence가 서로 다른 것이기 때문이다.

문제의 의도에 충실하려면, 서로 연결된 string들끼리만 substring을 구성할 수 있다. 문자열을 건너뛰거나 다른 조합은 안된다는 것.

 

예를들어 hdklqkcssgxlvehva 문자열 같은 경우 최대 중복개수는 2인데, 고유한 알파벳으로만 구성된 최소의 substring은 아래처럼 4가 되어야 한다. (순차적으로 담아야함)

• hdklq
• kcss
• sgxlveh
• va

 

trial2

 

모든 케이스를 패스하는 코드는 아래와 같이 구할 수 있다. 

• 현재의 substring인 lst를 초기화, 총 substring 개수인 count를 1로 초기화 
• 문자열 s를 돌면서 
• 요소 i가 lst에 포함되어있다면, 중복을 방지하기 위해 새로운 현재 lst를 생성하고, count를 1개 증가한다 (substring +1)
• 모든 경우에 lst에 i를 append한다 
• 최소의 count를 반환한다 

class Solution(object):
    def partitionString(self, s):
        count = 1
        lst = []

        for i in s : 
            if i in lst : 
                lst = []
                count += 1
                
            lst.append(i)
        return count