[leetcode] 1422. Maximum Score After Splitting a String (python)

문제 : https://leetcode.com/problems/maximum-score-after-splitting-a-string/

난이도 : Easy

 

풀이 1

class Solution:
    def maxScore(self, s: str) -> int:
        
        maxScore = 0
        
        for i in range(1, len(s)):
            cnt = s[:i].count('0') + s[i:].count('1')
            
            maxScore = max(cnt, maxScore)
        
        return maxScore

단순하게 index를 기준으로 왼쪽은 0의 갯수를, 오른쪽은 1의 갯수를 세서 최댓값을 구하는 풀이이다.

 

풀이 2

class Solution:
    def maxScore(self, s: str) -> int:
        # 왼쪽 0의 갯수 + 오른쪽 1의 갯수  
        # 왼쪽 0의 갯수 + (총 1의 갯수 - 왼쪽 1의 갯수)
        # 총 1의 갯수 + (왼쪽 0의 갯수 - 왼쪽 1의 갯수)
        
        zeros = 0
        ones = 0
        maxScore = float('-inf')
        
        for i in range(len(s)):
            if s[i] == '0':
                zeros += 1
            else:
                ones += 1
            
            if i != len(s) - 1:
                maxScore  = max(maxScore,  zeros - ones)
            
        
        return maxScore + ones

조금 더 논리적이게 식으로 생각해볼 수 있다.

구하고자 하는 값은 max(왼쪽 0의 갯수 + 오른쪽 1의 갯수) 이다. 이것은 아래와 같이 풀어낼 수 있다.

max(왼쪽 0의 갯수 + 오른쪽 1의 갯수)
= max(왼쪽 0의 갯수 + (총 1의 갯수 - 왼쪽  1의 갯수)
= 총 1의 갯수(const) + max(왼쪽 0의 갯수 - 왼쪽 1의 갯수)

for문이 끝나고 나면 ones는 총 1의 갯수가 될 것이므로 최대값 maxScore 에 ones를 더해서 리턴하면 된다. 
여기서 maxScore를 음수로 초기화한 이유는 '1111' 를 예시로 생각해보면 이해가 쉽다.

 

풀이 2는 오른쪽 값은 전혀 신경쓰지 말자는 의미에 풀이이긴 하지만 사실 풀이1이나 2나 별반 차이 없다.