1422. Maximum Score After Splitting a String

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

Difficulty : Easy

Status : Solved

Time : 00:04:33

---

문제 설명

 

0, 1로 구성된 문자열 s가 주어졌을 때, 이 문자열을 비어있지 않은 부분 문자열 둘로 나눴을 때 최대 스코어를 반환하라.

문자열을 나눈 후의 스코어는 왼쪽 부분문자열의 0의 개수와 오른쪽 부분문자열의 1의 개수의 합이다.

---

 

풀이

 

약간의 창의력 문제.

오른쪽의 1의 개수를 먼저 다 세 놓고, 모든 split case를 슬라이딩 윈도우(즉 포인터를 하나씩 옮겨가며) 방식으로 구해볼 수 있다.

만약 나누는 부분이 1이면 이면 오른쪽 점수가 1 감소(오른쪽의 1이 하나 왼쪽으로 가는 셈이므로), 0이면 왼쪽 점수가 1 증가하는 식이다.

 

풀이 코드

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