[코테연습] 1422. Maximum Score After Splitting a String

https://leetcode.com/problems/maximum-score-after-splitting-a-string/description/?envType=daily-question&envId=2025-01-01

 

문제타입

• 문자열 처리 (String Manipulation)
• 슬라이딩 윈도우 (Sliding Window)
• 최대화 문제 (Maximization Problem)

---

문제분석

• 주어진 문자열 s를 왼쪽 부분과 오른쪽 부분으로 나누었을 때,
  왼쪽 부분에서의 '0'의 개수와 오른쪽 부분에서의 '1'의 개수의 합이 최대가 되도록 해야 함.
• 나눌 수 있는 위치는 s.length() - 1 개.
• 문자열의 각 문자에 대해 조건에 따라 카운팅하고, 매 위치에서 최대값을 갱신하며 답을 구해야 함.
• 시간 복잡도를 줄이기 위해 슬라이딩 윈도우 또는 누적합을 활용하는 방식 적합.

---

문제풀이

1. 초기 상태 설정:
   • 전체 문자열의 '1'의 개수를 세어 right에 저장.
   • left는 처음에 0으로 시작하며, 이는 '0'의 개수를 누적 저장.
2. 첫 번째 분할 고려:
   • 첫 번째 문자가 '0'이면 left를 1 증가, '1'이면 right를 1 감소.
   • 초기 max를 left + right로 설정.
3. 슬라이딩 윈도우 구현:
   • 문자열을 두 번째 문자부터 마지막 전 문자까지 순회:
     • 현재 문자가 '0'이면 left 증가.
     • 현재 문자가 '1'이면 right 감소.
     • max를 left + right와 비교하여 더 큰 값으로 갱신.
4. 특수 케이스 처리:
   • 문자열 길이가 2인 경우, 바로 max 반환.
5. 결과 반환:
   • 최대값 max를 반환.

 

> java

 

class Solution {
    public int maxScore(String s) {
        int n = s.length();
        int max = 0;
        int left = 0;
        int right = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') {
                right+=1;
            }
        }
        if (s.charAt(0) == '0'){
            left+=1;
        } else {
            right-=1;
        }
        max = left+right;

        if ( n == 2) {
            return max;
        }
        for (int i = 1; i < n-1; i++) {
        
            if (s.charAt(i) == '0') {
                left+=1;
            } else {
                right-=1;
            }
            max = Math.max(right+left, max);
            
        }

        return max;
    }
}

 

> python

 

class Solution:
    def maxScore(self, s: str) -> int:
        n = len(s)
        max_score = 0
        left = 0
        right = 0

        # Count initial number of '1's in the string
        for char in s:
            if char == '1':
                right += 1

        # Initialize with the first split
        if s[0] == '0':
            left += 1
        else:
            right -= 1
        max_score = left + right

        # Special case for string length 2
        if n == 2:
            return max_score

        # Iterate from the second character to the second-to-last character
        for i in range(1, n - 1):
            if s[i] == '0':
                left += 1
            else:
                right -= 1
            max_score = max(left + right, max_score)

        return max_score