[LeetCode | Java | Greedy 문제 풀이] 1221. Split a String in Balanced Strings - Solution with Loop of forEach Statement

99클럽 | 비기너

👆🤞1221. Split a String in Balanced Strings

🏷 Topic : String Greedy Counting

Easy

Balanced strings are those that have an equal quantity of 'L' and 'R' characters.

Given a balanced string s, split it into some number of substrings such that:

• Each substring is balanced.

Return the maximum number of balanced strings you can obtain.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'.
Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints:

• 2 <= s.length <= 1000
• s[i] is either 'L' or 'R'.
• s is a balanced string.

Accepted   304.3K  |  Submissions    353.5K  |  Acceptance Rate    86.1%

---

✔ Solution with Loop of for Statement

class Solution {
    public int balancedStringSplit(String s) {
        int cntL = 0;
        int cntR = 0;
        int cnt = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'L') {
                cntL++;
            } else {
                cntR++;
            }

            if (cntL == cntR) {
                cnt++;
                cntL = 0;
                cntR = 0;
            }
        }
        return cnt;
    }
}

채점 결과

---

✔ Solution with Loop of forEach Statement1

class Solution {
    public int balancedStringSplit(String s) {
        char[] cArr = s.toCharArray();
        int cnt = 0;
        int cntL = 0;
        int cntR = 0;

        for (char c : cArr) {
            if (c == 'L') {
                cntL++;
            } else {
                cntR++;
            }

            if (cntL == cntR) {
                cnt++;
                cntL = 0;
                cntR = 0;
            }
        }

        return cnt;
    }
}

채점 결과

---

✔ Solution with Loop of forEach Statement2

class Solution {
    public int balancedStringSplit(String s) {
        String[] sArr = s.split("");
        int cnt = 0;
        int cntL = 0;
        int cntR = 0;

        for (String s1 : sArr) {
            if (s1.equals("L")) {
                cntL++;
            } else {
                cntR++;
            }

            if (cntL == cntR) {
                cnt++;
                cntL = 0;
                cntR = 0;
            }
        }

        return cnt;
    }
}

채점 결과

---

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 문제의 Point! : Balanced String을 잘라 최대로 만들 수 있는 Balanced String의 수를 반환하시오.

• Balanced String : 'L'과 'R'의 문자 개수가 같은 문자열

Balanced String을 잘라 나온 Balanced String은

문자열의 시작 인덱스부터 마지막 인덱스까지 'L'과 'R'을 세었을 때, 'L'과 'R'의 개수가 같아야하므로
for문으로 String s의 첫문자부터 'L'과 'R'을 세어서

'L'의 개수와 'R'의 개수가 같아지는 지점을 기준으로 문자열을 잘라
총 몇개의 Balanced String이 나오는지 알아보자.

1. 문자 'L'을 셀 int cntL을 0으로 초기화.

int cntL = 0;

2. 문자 'R'을 셀 int cntR을 0으로 초기화.

int cntR = 0;

3. 잘려 나온 Balanced String의 개수를 셀 int cnt를 0으로 초기화

int cnt = 0;

4. for문을 돌려 String s의 문자를 하나하나 검사하자.

for (int i = 0; i < s.length(); i++) {
    ...
}

5. 만약 현재 인덱스의 문자가 'L'이면 cntL값 1 증가

if (s.charAt(i) == 'L') {
    cntL++;
}

6. 위의 경우가 아니라면 현재 인댁스의 문자는 'R'이므로 cntR 값 1 증가

else {
    cntR++;
}

7. 자른 문자열의 시작부터 현재 인덱스까지 cntL과 cntR이 같으면
   현재 인덱스까지 자른 문자열은 Balanced String이 된다.

cnt 값 1 증가
cntL과 cntR은 0으로 초기화 해주자.

if (cntL == cntR) {
    cnt++;
    cntL = 0;
    cntR = 0;
}

8. cnt가 s를 잘라 나온 Balanced String의 개수이므로 for문이 끝나면 cnt를 반환하자.

return cnt;

💬 무엇을 새롭게 알았는지

코딩 스터디를 하면서 코드장님께서 toCharArray()로도 forEach문을 돌릴 수 있다고 하셔서
코드를 한번 다시 써 보았다.

코드장님께서 탐욕법(Greedy)으로 접근해야 하는 문제는 보통 이런식으로 나온다고 하셨다.

• '경로, 건물 길이를 주고 최소한의 ~를 구하세요.'라는 형식으로 주로 출제됨.
• '시작점'과 '끝점'이 주어짐.

탐욕법을 풀때는 정렬을 하고 시작!

---

🆙 Next Level

• 미들러 : 🛟 구명보트
• 챌린저 : 📸 단속카메라