본문 바로가기

알고리즘/그리디

Split a String in Balanced Strings

문제 링크

리트코드에서 본 모법답안

public int balancedStringSplit(String s) {
    int res = 0, cnt = 0;        //res는 나눠질 수 있는 갯수, cnt는 L이 있으면 ++, R이면 --.
    for (int i = 0; i < s.length(); ++i) {
        cnt += s.charAt(i) == 'L' ? 1 : -1;
        if (cnt == 0) ++res;        //cnt가 0인 경우는 R과 L의 갯수가 같은 경우, 즉 나줘질 수 있을 때 밖에 없음.
    }
    return res;             
}  

위 코드의 경우, 갯수를 초기화 할 필요도 없고 변수를 두개나 할 필요도 없음.

답지 보기 전에 푼 거.

class Solution {
    public int balancedStringSplit(String s) {
        int answer = 0;        //나눠질 수 있는 갯수.
        int numOfR = 0;        //R의 갯수.
        int numOfL = 0;        //L의 갯수.

        for (char c : s.toCharArray()) {
            switch (c) {        //문자의 따라 R이나 L의 갯수를 증가 시킴.
                case 'R' : numOfR++;
                            break;
                case 'L' : numOfL++;
                            break;
            }
            if (numOfR == numOfL) {    //R과 L의 갯수가 같아지면, 문자열로 나눠진다. 
                answer++;
                numOfL = 0;        //L의 갯수를 초기화.
                numOfR = 0;        //R의 갯수를 초기화.
            }
        }
        return answer;
    }
}

문제의 제일 중요한 조건이 Balanced strings are those that have an equal quantity of 'L' and 'R' characters.
L과 R의 갯수가 같다는 것.

728x90
반응형

'알고리즘 > 그리디' 카테고리의 다른 글

942. DI String Match  (0) 2021.08.11
561. Array Partition I  (0) 2021.07.25
1710. Maximum Units on a Truck  (0) 2021.06.23
Minimum Subsequence in Non-Increasing Order  (0) 2021.04.08
Number Of Rectangles That Can Form The Largest Square  (0) 2021.04.06