[99클럽 코테 스터디] 6일차 TIL - 탐욕법(Greedy), Split a String in Balanced Strings

[6일차] 탐욕법(Greedy)

 

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

* 대충번역: 같은 수의 'L'과 'R'을 가진 문자열을 균형잡힌(balanced) 문자열이라고 한다. 균형잡힌 문자열 s가 주어졌을 때, 문자열을 쪼개었을 때도 균형잡힌 문자열이 되도록 하는 최대 문자열의 개수를 반환하라.

Solution

class Solution(object):
    def balancedStringSplit(self, s):
        """
        :type s: str
        :rtype: int
        """

        result = 0
        rnum = 0
        lnum = 0
        
        for i in s:
            if i == 'R':
                rnum += 1
            if i == 'L':
                lnum += 1
            
            if rnum == lnum:
                result += 1
                rnum = 0
                lnum = 0
            
        return result

Better Solution

찾아야 하는 것은 균형잡힌 문자열의 갯수이다. 균형잡힌 문자열은 L과 R의 갯수가 같아야 한다.

그러나 L과 R의 갯수를 세는 것이 필수적인 것은 아니다. "균형"의 여부만 확인하면 되기 때문이다. 어려운 문제에 응용할 수 있는 접근법 같다.

 

class Solution(object):
    def balancedStringSplit(self, s):
        count = 0
        balance = 0

        for char in s:
            if char  == 'R':
                balance += 1
            else:
                balance -= 1

            if balance == 0:
                  count +=1

        return count

나다어

• 구해야 하는 것이 무엇인지를 정의하자. 해결의 방향성이 잡힌다.
• 쉬운 문제여서 어디가 그리디 알고리즘일까 싶긴 하지만, 차례대로(그리디는 정렬과 자주 쓰인다.) 해결해나간다는 점을 확인하면 될 것 같다.