1422. Maximum Score After Splitting a String

문제 링크


내 코드

다 해보기.

0ms, 8.6MB

class Solution {
public:
    int maxScore(string s) {
        int n = s.size();
        int answer{};
        for(int i{1};i < n; ++i) {
            answer = max(answer, countZero(s, 0, i) + countOne(s, i, n));
        }
        return answer;
    }
    int countZero(string& str, int s, int e) {
        int cnt{};
        for(int i{s};i<e;++i) {
            if(str[i] == '0') ++cnt;
        }
        return cnt;
    } 
    int countOne(string& str, int s, int e) {
        int cnt{};
        for(int i{s};i<e;++i) {
            if(str[i] == '1') ++cnt;
        }
        return cnt;
    } 
};

Solution

Approach 1: Brute Force

  • 4ms, 8.73MB
  • Complexity
    • Given nn as the length of nums
    • Time Complexity: O(n2)O(n^2)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int maxScore(string s) {
        int ans = 0;
        for (int i = 0; i < s.size() - 1; i++) {
            int curr = 0;
            for (int j = 0; j <= i; j++) {
                if (s[j] == '0') {
                    curr++;
                }
            }
            
            for (int j = i + 1; j < s.size(); j++) {
                if (s[j] == '1') {
                    curr++;
                }
            }
            
            ans = max(ans, curr);
        }
        
        return ans;
    }
};

GPT

이 코드는 주어진 문자열 s를 두 개의 부분 문자열로 나누었을 때, 왼쪽 부분에는 '0'의 개수를 최대화하고 오른쪽 부분에는 '1'의 개수를 최대화하는 방법을 찾고, 그 합의 최댓값을 반환하는 문제를 해결하는 코드입니다.

코드 분석

  1. 입력 및 변수 선언

    • 문자열 s가 주어짐.
    • ans 변수를 선언하여 최대 점수를 저장함.

  2. 문자열을 나누는 기준 설정

    • for 루프를 사용하여 i를 0부터 s.size() - 2까지 이동하면서 문자열을 두 부분으로 나눔.
      • i는 왼쪽 부분의 마지막 인덱스를 의미함.
      • 즉, 왼쪽 부분은 s[0]부터 s[i]까지, 오른쪽 부분은 s[i+1]부터 s[s.size() - 1]까지.

  3. 각 부분에서 0과 1의 개수 세기

    • curr 변수를 사용하여 현재 점수를 저장함.
    • s[0] ~ s[i]에서 '0'의 개수를 셈.
    • s[i+1] ~ s[s.size()-1]에서 '1'의 개수를 셈.
    • curr 값이 가장 큰 경우를 ans에 저장.

  4. 최종 결과 반환

    • ans에 저장된 최대 점수를 반환함.

예제 입력 및 실행 과정

예제 1

string s = "011101";
Solution sol;
cout << sol.maxScore(s);

실행 과정

  • i = 0 → "0" | "11101" → 1(0의 개수) + 4(1의 개수) = 5
  • i = 1 → "01" | "1101" → 1 + 3 = 4
  • i = 2 → "011" | "101" → 1 + 2 = 3
  • i = 3 → "0111" | "01" → 1 + 1 = 2
  • i = 4 → "01110" | "1" → 2 + 1 = 3

최댓값은 5.

시간 복잡도 분석

  • for (int i = 0; i < s.size() - 1; i++): O(n)
  • 내부의 두 개의 for 문:
    • for (int j = 0; j <= i; j++): 최악의 경우 O(n)
    • for (int j = i + 1; j < s.size(); j++): 최악의 경우 O(n)

총 시간 복잡도: O(n2)O(n^2) (비효율적)


Approach 2: Count Left Zeros and Right Ones

  • 0ms, 8.69MB
  • Complexity
    • Given nn as the length of nums
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int maxScore(string s) {
        int ones = count(s.begin(), s.end(), '1');
        
        int ans = 0;
        int zeros = 0;
        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == '1') {
                ones--;
            } else {
                zeros++;
            }
            
            ans = max(ans, zeros + ones);
        }
        
        return ans;
    }
};

GPT

이 코드는 문자열 s를 두 부분으로 나누었을 때, 왼쪽 부분에 포함된 '0'의 개수와 오른쪽 부분에 포함된 '1'의 개수의 합을 최대화하는 문제를 더 효율적으로 해결하는 방식입니다.

🔍 코드 분석

1️⃣ 전체 ‘1’ 개수 세기

int ones = count(s.begin(), s.end(), '1');
  • 문자열 s 전체에서 '1'의 개수를 세어 ones 변수에 저장합니다.
  • 이렇게 하면, 나중에 왼쪽 부분이 확장될 때 오른쪽 부분의 ‘1’ 개수를 빠르게 업데이트할 수 있습니다.
  • count() 함수의 시간 복잡도는 O(n)입니다.

2️⃣ 왼쪽에서 한 글자씩 이동하면서 최댓값 찾기

int ans = 0;
int zeros = 0;
for (int i = 0; i < s.size() - 1; i++) {
  • ans: 최댓값 저장
  • zeros: 왼쪽 부분의 '0' 개수 저장
  • i를 0부터 s.size() - 2까지 반복하여 왼쪽 부분을 확장해 나감.

3️⃣ 왼쪽 부분의 ‘0’ 개수 & 오른쪽 부분의 ‘1’ 개수 관리

if (s[i] == '1') {
    ones--;  // 오른쪽 부분의 '1' 개수를 줄임
} else {
    zeros++; // 왼쪽 부분의 '0' 개수를 증가
}
  • 왼쪽 부분이 확장될 때:
    • s[i]가 '1'이면, 오른쪽 부분에서 '1' 하나가 사라지므로 ones--
    • s[i]가 '0'이면, 왼쪽 부분에서 '0'이 하나 추가되므로 zeros++

4️⃣ 현재 분할 상태의 점수 갱신

ans = max(ans, zeros + ones);
  • zeros + ones는 현재 분할 상태에서 얻을 수 있는 점수입니다.
  • ans에 최댓값을 저장.

5️⃣ 최종 결과 반환

return ans;
  • ans에 저장된 최대 점수를 반환.

📌 예제 실행

string s = "011101";
Solution sol;
cout << sol.maxScore(s);

실행 과정

i왼쪽 부분오른쪽 부분zerosoneszeros + ones
0"0""11101"134
1"01""1101"123
2"011""101"112
3"0111""01"112
4"01110""1"213

최댓값은 4.

⏱ 시간 복잡도 분석

연산시간 복잡도
count(s.begin(), s.end(), '1')O(n)O(n)
for 루프 (O(n))O(n)O(n)
전체 시간 복잡도O(n)O(n)

이전 코드의 O(n2)O(n^2) 보다 훨씬 효율적이며, 선형 시간 O(n)O(n)에 해결할 수 있습니다! 🚀

💡 핵심 최적화 포인트

  1. count()를 사용하여 초기 ones를 빠르게 계산 → O(n)O(n)
  2. 왼쪽 부분이 확장될 때 오른쪽 부분의 ‘1’ 개수를 효율적으로 업데이트 → O(n)O(n)
  3. 한 번의 for 루프로 문제 해결 → O(n)O(n)

✅ 결론

이 코드는 최적화된 O(n)O(n) 풀이법을 사용하여 문제를 해결합니다.
한 번의 for 루프만으로 빠르게 최대 점수를 찾을 수 있는 효과적인 방법입니다! 🚀


Approach 3: One Pass

  • 0ms, 8.70MB
  • Complexity
    • Given nn as the length of nums
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int maxScore(string s) {
        int ones = 0;
        int zeros = 0;
        int best = INT_MIN;

        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] == '1') {
                ones++;
            } else {
                zeros++;
            }
            
            best = max(best, zeros - ones);
        }
        
        if (s[s.size() - 1] == '1') {
            ones++;
        }
        
        return best + ones;
    }
};

GPT

이 코드는 문자열 s를 두 부분으로 나누어 왼쪽 부분에서 '0'의 개수를 최대화하고, 오른쪽 부분에서 '1'의 개수를 최대화하는 문제를 해결하는 효율적인 방법을 사용합니다.

하지만 기존 풀이 방식과 차이가 있는 점은:

  • zeros - ones를 사용하여 최적 점수를 계산
  • 마지막 문자의 '1' 개수를 별도로 추가

🔍 코드 분석

1️⃣ 변수 초기화

int ones = 0;
int zeros = 0;
int best = INT_MIN;
  • ones: 현재까지 등장한 '1'의 개수
  • zeros: 현재까지 등장한 '0'의 개수
  • best: 최적 점수를 저장 (INT_MIN으로 초기화)

2️⃣ 문자열을 순회하며 왼쪽 부분 점수 계산

for (int i = 0; i < s.size() - 1; i++) {
  • s를 왼쪽 부분 (s[0] ~ s[i])과 오른쪽 부분 (s[i+1] ~ s[s.size()-1])으로 나누는 방식
  • 마지막 문자는 오른쪽 부분에 남겨두기 위해 i < s.size() - 1까지만 탐색

3️⃣ 현재까지의 ‘0’과 ‘1’ 개수 세기

if (s[i] == '1') {
    ones++;  // 왼쪽에 '1'이 포함되면 증가
} else {
    zeros++; // 왼쪽에 '0'이 포함되면 증가
}
  • zeros: 왼쪽 부분에 포함된 '0' 개수
  • ones: 왼쪽 부분에 포함된 '1' 개수

4️⃣ 최적 점수 갱신

best = max(best, zeros - ones);
  • zeros - ones를 사용하여 최적 점수를 계산
  • 왼쪽 부분에서 ‘0’을 최대화하고 ‘1’을 최소화하는 것이 유리
    • '0'은 점수를 증가시키고, '1'은 점수를 감소시키므로
    • zeros - ones가 클수록 좋은 분할이 됨
  • 최댓값을 best에 저장

5️⃣ 마지막 문자가 ‘1’인지 확인하여 추가

if (s[s.size() - 1] == '1') {
    ones++;
}
  • 마지막 문자는 오른쪽 부분에 포함되므로, '1'이면 ones++
  • 기존 best 값에 최종 ones 개수를 더함.

6️⃣ 최종 결과 반환

return best + ones;
  • 최적 best 값과 마지막 오른쪽 부분의 '1' 개수를 더한 결과를 반환.

📌 예제 실행

string s = "011101";
Solution sol;
cout << sol.maxScore(s);

실행 과정

i왼쪽 부분오른쪽 부분zerosoneszeros - onesbest
0"0""11101"101 - 0 = 11
1"01""1101"111 - 1 = 01
2"011""101"121 - 2 = -11
3"0111""01"131 - 3 = -21
4"01110""1"232 - 3 = -11

최댓값 best = 1, 그리고 마지막 '1'이 추가되므로 1 + 3 = 4.

💡 핵심 최적화 포인트

  1. zeros - ones를 사용하여 왼쪽 부분의 최적 점수를 찾음
  2. 마지막 문자를 따로 처리하여 오른쪽 부분의 '1' 개수를 고려
  3. O(n) 단일 루프로 해결 가능하여 효율적