[99클럽 코테 스터디 17일차 TIL] LeetCode | 1221. Split a String in Balanced Strings

17일차 알고리즘

 

Problem

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

 

 

Sol

문자열 내 L과 R의 균형을 이루는 문자열의 개수를 카운트하는 문제

 

 

Greedy Algorithm 

🌱 참고

이전 글에 탐욕 알고리즘을 정리해두었습니다.

[99클럽 코테 스터디 17일차 TIL] 프로그래머스 | Greedy 구명보트

 

 

해결 방법

 

👀 시소처럼 생각해서 L이라면 balance+=1, R이라면 balance-=1 하여서 balance가 0이라면 균형이 맞아진다는 방식으로 접근하였습니다.

[변수]
bal_cnt : 균형이 맞는 문자열의 수를 count한 값을 저장하는 변수(최종 결과값)
balance : 값이 -1, +1 씩 변화함에 따라 0이 되면 균형이 맞음을 알려주는 변수

1. 주어진 str 순회
2. L 이라면 +1, R이라면 -1
3. 균형이 맞으면 해당 문자열 카운트 : balance가 0이되면 bal_cnt를 1 증가시킴
4. 문자열을 모두 순회하면 bal_cnt 반환

 

 

시간복잡도 O(n)

• 문자열(n개) 순회 : O(n)

---

✔ Answer

class Solution:
    def balancedStringSplit(self, s: str) -> int:
    	# 균형잡힌 문자열 카운트
        bal_cnt = 0
        # 'L'과 'R'의 균형 여부
        balance = 0
        
	# 1. 주어진 str 순회
        for char in s:
	# 2. L이라면 +1
            if char == 'L':
                balance += 1
 	# if char == 'R' 이라면 -1
            else:
                balance -= 1
        
	# 3. 균형이 맞았다! bal_cnt 증가
            if balance == 0:
                bal_cnt += 1
        
        return bal_cnt

---

💬 소감

오늘의 문제 주제 Greedy 에 대하여 비기너 문제를 풀어보았습니다. 당장 주어진 문자열에서 균형을 판단하는 것에서 Greedy Algorithm의 특징을 잘 알 수 있는 문제였습니다.