[LeetCode] 1422. Maximum Score After Splitting a String

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

Maximum Score After Splitting a String - LeetCode

leetcode - Maximum Score After Splitting a String

문제 유형 : 순회 / 다이나믹 프로그래밍

문제 난이도 : 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.

 

0과 1로 이루어진 문자열 s가 주어진다. 두 문자열을 나눴을 때 가장 큰 점수를 반환하시오,

점수 구하는 방법: 왼쪽 부분 문자열의 0의 개수 + 오른쪽 부분 문자열의 1의 개수

단, 각 부분 문자열의 길이는 적어도 1 이상이어야 합니다.

 

 

풀이

프로그래머스 롤케이크 자르기 문제와 아주 비슷하다. 이 문제보다 조금 더 어려우니 이 문제를 먼저 풀어보고 도전해보면 될 것 같다.

우선 한 번 배열을 순회하면서, 1의 개수를 카운트한다. 이 값은 처음의 오른쪽 부분 문자열의 개수이다.

배열을 한 번 더 순회한다. 인덱스 0부터 n-2까지 순회해준다.(적어도 부분 문자열의 길이가 1이어야 하므로)

• 만약 현재 순회하는 문자가 0이면, 왼쪽 점수를 1 증가한다.
• 1이라면, 오른쪽 점수를 1 감소시킨다.
• 최고 점수를 갱신해준다.

최고 점수를 반환해주면 된다.

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maxScore(string s) {
        const int n = s.size();
        int leftCount = 0;
        int rightCount = 0;
        int maxScore = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] == '1') rightCount++;
        }

        for(int i = 0; i < n-1; i++) {
            if(s[i] == '0') leftCount++;
            else rightCount--;
            maxScore = max(maxScore, leftCount + rightCount);
        }

        return maxScore;
    }
};