99클럽 코테 스터디 16일차 TIL + 탐욕법 Greedy, [leetcode] Split a String in Balanced Strings

✨ 문제 

Split a String in Balanced Strings

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.

 

https://leetcode.com/problems/split-a-string-in-balanced-strings/description/

 

 

 

✨ 개념

탐욕법 Greedy Algorithm

- 현재 상황에서 가장 최적의 선택을 하는 알고리즘.

- 그 상황에서 가장 좋은 선택을 하기 때문에 최종값이 최적의 결과임을 보장하지 않음.

- 값들이 서로 영향을 주면 안됨.

 

 

 

✨ 최종코드

class Solution {
    public int balancedStringSplit(String s) {
        int balance = 0;
        int count = 0;
        
        for (char c : s.toCharArray()) {
            if (c == 'L')
                balance++;
            else if (c == 'R')
                balance--;
            
            if (balance == 0)
                count++;
        }
        
        return count;   
    }
}