오늘의 주제도 탐욕법(Greedy)
[Split a String in Balanced Strings]
문제
입력과 출력
코딩
class Solution:
def balancedStringSplit(self, s: str) -> int:
r_cnt=0
l_cnt=0
answer=0
for i in range(len(s)):
if s[i]=='R':
r_cnt+=1
else:
l_cnt+=1
if r_cnt==l_cnt:
answer+=1
return answer알고리즘
r과 l의 개수를 세기 위한 변수를 정의해주고,
문자열이 R일때 r_cnt+1
문자열이 L일때 l_cnt+1
이 수가 같아졌을 때 answer+1
회고
먼저, 문제를 이해하느라 오래걸렸는데
이해하고 나서는 ,, 이거 대칭성도 고려해줘야 하는거 아닌가?
그냥 비교해서 되나..?
수가 바뀔때마다 새로 비교해야하는거 아닐까..?
하는 생각들때문에 오래걸렸는데
결론은 반례를 아무리 들어도 없었다.
R이 1개일때, L이 섞여서 3개가 되는동안 R은 하나이면 어떡하지? 했는데
ex)RLRRL---
이런식으로 예를 들었는데, 이미 2번 요소에서 r과 l의 수가 같아져서 반환하고, r 세어지고.
마지막 다음에 r이 나온다고 하더라도 대칭이 안되니까 아직 안세어지는..? 이런식으로 생각했다.
ex)LLRLRRLL--
이런식으로 되면 그냥 개수가 같아질때까지 해서 그때까지가 한묶음인것..
애초에 알고리즘 파악을 잘못했던 것이었다!
개수만 고려해서 비교했을 때 반례가 있을 수가 없는 문제였던 것..!!
이런식으로 대칭성 고려를 잘못 생각하고 열심히 짜고있었다,,
도저히 감이 안와서 그냥 처음 생각했던 걸로
개수 비교를 통해 문제를 해결했는데
진짜 될줄 몰랐다..!
그래서 반례를 들어가면서 다시 문제를 상기했는데
위에서 설명했던 결과들이 나왔던 것,,
처음 생각했던 알고리즘이 맞았었다!
공부..일기....