99클럽 코테 스터디 8일차 TIL +탐욕법 Greedy(2)

오늘의 공부 키워드

• 탐욕법(greedy)
• 1221. Split a String in Balanced Strings

문제 해석

문제는 'L'과 'R' 문자가 같은 수만큼 있는 문자열 s가 주어졌을 때, 이를 'L'과 'R'이 같은 수만큼 포함된 부분 문자열들로 최대 몇 개로 나눌 수 있는지를 찾는 것입니다.

 

문제 해결 방법

1. 균형잡힌 문자열: 문자열이 균형잡혔다면, 'L'과 'R'의 수가 동일하다는 뜻입니다. 예를 들어 "RL", "RLRL", "RRLL" 등이 있습니다.
2. 부분 문자열 나누기: 주어진 문자열을 여러 개의 균형잡힌 부분 문자열로 나눠야 합니다. 예를 들어 "RLRRLLRLRL"을 "RL", "RRLL", "RL", "RL"로 나누면 각 부분 문자열이 'L'과 'R'이 동일한 수를 가집니다.

해결 방법 단계별 설명

1. 카운터 변수 사용: 'L'과 'R'의 개수를 세기 위해 카운터 변수를 사용합니다.
2. 부분 문자열 나누기: 문자열을 순서대로 탐색하면서 'L'을 만나면 카운터를 증가시키고, 'R'을 만나면 카운터를 감소시킵니다. 카운터가 0이 되는 순간, 하나의 균형잡힌 부분 문자열을 찾았음을 의미합니다.
3. 결과 값 증가: 카운터가 0이 될 때마다 결과 값을 증가시킵니다.

코드 설명

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = 0
        count = 0

        for char in s:
            if char == 'R':
                balance -= 1
            else:  # char == 'L'
                balance += 1
            
            if balance == 0:
                count += 1
        
        return count

 

코드 설명

1. 클래스 정의: class Solution을 정의합니다.
2. 메서드 정의: 클래스 내부에 balancedStringSplit이라는 메서드를 정의합니다. 이 메서드는 문자열 s를 매개변수로 받아 균형잡힌 문자열의 최대 개수를 반환합니다.
3. 변수 초기화:
   • balance: 'L'과 'R'의 균형을 맞추기 위한 변수입니다. 초기값은 0입니다.
   • count: 균형잡힌 문자열의 개수를 세기 위한 변수입니다. 초기값은 0입니다.
4. 문자열 순회:
   • for char in s: 문자열 s의 각 문자를 하나씩 순회합니다.
5. 균형 맞추기:
   • if char == 'R': 현재 문자가 'R'인 경우, balance를 1 감소시킵니다.
   • else: 현재 문자가 'L'인 경우, balance를 1 증가시킵니다.
6. 균형잡힌 문자열 찾기:
   • if balance == 0: balance가 0이 되는 순간, 균형잡힌 문자열을 찾은 것입니다.
   • count += 1: 균형잡힌 문자열을 찾았으므로 count를 1 증가시킵니다.
7. 결과 반환:
   • return count: 최종적으로 찾은 균형잡힌 문자열의 개수를 반환합니다.

예시사용법

# 예시 입력
s1 = "RLRRLLRLRL"
s2 = "RLRRRLLRLL"
s3 = "LLLLRRRR"

solution = Solution()
print(solution.balancedStringSplit(s1))  # 출력: 4
print(solution.balancedStringSplit(s2))  # 출력: 2
print(solution.balancedStringSplit(s3))  # 출력: 1

이 코드를 통해 주어진 문자열 s를 최대한 많은 균형잡힌 문자열로 나눌 수 있습니다. 각 문자에 따라 균형을 맞추고, 균형이 맞을 때마다 개수를 세어 최종 결과를 반환합니다.

 

오늘의 회고

 

• 문제 해석력을 높여야겠다.
• 좀더 끈질기게 고민하고 문제를 풀어야 하는데 쉽게 포기하는게 아닌가 하고 반성하게 된다.
• 코드 리뷰라고 하더라도 문제를 이해하는게 정말 중요함을 느낀다.
• 코딩테스트 문제만 풀지말고 기록도 남겨야 함을 느낀다.
• 알고리즘에 대한 공부를 더 해야할것을 느낀다.