알고리즘 문제 풀이/그리디
Split a String in Balanced Strings
가나무마
2021. 4. 6. 16:45
문제 링크


리트코드에서 본 모법답안
public int balancedStringSplit(String s) {
int res = 0, cnt = 0; //res는 나눠질 수 있는 갯수, cnt는 L이 있으면 ++, R이면 --.
for (int i = 0; i < s.length(); ++i) {
cnt += s.charAt(i) == 'L' ? 1 : -1;
if (cnt == 0) ++res; //cnt가 0인 경우는 R과 L의 갯수가 같은 경우, 즉 나줘질 수 있을 때 밖에 없음.
}
return res;
}
위 코드의 경우, 갯수를 초기화 할 필요도 없고 변수를 두개나 할 필요도 없음.
답지 보기 전에 푼 거.
class Solution {
public int balancedStringSplit(String s) {
int answer = 0; //나눠질 수 있는 갯수.
int numOfR = 0; //R의 갯수.
int numOfL = 0; //L의 갯수.
for (char c : s.toCharArray()) {
switch (c) { //문자의 따라 R이나 L의 갯수를 증가 시킴.
case 'R' : numOfR++;
break;
case 'L' : numOfL++;
break;
}
if (numOfR == numOfL) { //R과 L의 갯수가 같아지면, 문자열로 나눠진다.
answer++;
numOfL = 0; //L의 갯수를 초기화.
numOfR = 0; //R의 갯수를 초기화.
}
}
return answer;
}
}
문제의 제일 중요한 조건이 Balanced strings are those that have an equal quantity of 'L' and 'R' characters.
L과 R의 갯수가 같다는 것.