[LeetCode] 1422. Maximum Score After Splitting a String (Python)

 

난이도: Easy

 

문제 설명

---

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

 

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

 

문제 예제

---

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

 

제한 사항

---

• 2 <= s.length <= 500
• The string s consists of characters '0' and '1' only.

 

✏️ Solution(솔루션)

---

class Solution:
    def maxScore(self, s: str) -> int:
        answer = 0

        dic_left = {'0':0, '1':0}
        dic_right = {'0':0, '1':0}
        
        for num in s:
            dic_right[num] += 1
        
        for i in range(len(s)-1):
            dic_right[s[i]] -= 1
            dic_left[s[i]] += 1
            answer = max(answer, dic_right['1'] + dic_left['0'])

        return answer

 

먼저 '0'과 '1'을 key로 갖는 딕셔너리 2개를 만들었다.

 

하나는 left를 가리키는 딕셔너리이고 하나는 right를 가리키는 딕셔너리이다.

 

초기에 left 딕셔너리가 갖는 key들의 value를 모두 0으로 설정하고 right는 s가 가지고 있는 '0'과 '1'의 개수를 value로 설정한다.

 

그리고 s에 각 요소마다 dic_left[s[i]]는 +1을 하고 dic_right[s[i]]는 -1을 해준다.

다음으로 max함수를 통해(answer = max(answer, dic_right['1'] + dic_left['0'])) 제일 큰 값을 answer에 저장하고, 정답으로 return 하였다.

 

---

문제: 1422. Maximum Score After Splitting a String

깃허브: github

algorithm_practice/LeetCode/1537-maximum-score-after-splitting-a-string at main · laewonJeong/algorithm_practice