Split a String in Balanced Strings

 

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

불러오는 중입니다...

 

스택을 이용하여 문자열에 페어를 맞춰주는 문제

RLRRLLRLRL 문자열이 주어 질때 표로 그리면 아래와 같을 수 있다.

 

문자열	TOP	DESCRIPTION
R	EMPTY	스택에 아무것도 없으니 삽입
RL	R	스택에 탑이 임으로 POP 한다. COUNT 증가
RLR	EMPTY	스택에 아무것도 없으니 삽입
RLRL	R	스택에 탑이 임으로 POP 한다. COUNT 증가
RLRLR	EMPTY	스택에 아무것도 없으니 삽입
RLRLRR	R	이전 스택이 같으므로 삽입
RLRLRRL	R	스택이 탑이 R 임으로 POP 스택이 비어있는지 확인 하고 COUNT 증가
RLRLRRLL	R	스택이 탑이 R 임으로 POP 스택이 비어있는지 확인 하고 COUNT 증가

 

R 과 L 의 페어를 맞추며 R 들어오고 그다음에 L 이 들어오면 POP 을 한다.

스택이 비어 있으면 Solution 의 값을 증가 한다.

단순히 스택으로 풀 수 있는 문제

 

class Solution {
public:
    int balancedStringSplit(string s) {
        int sol = 0;

        stack<char> st;
        for (int i = 0; i < s.size(); i++) {

            char code = s[i];
            if (st.empty()) {
                st.push(code);
            }
            else {

                char top = st.top();

                if (top == code) {
                    st.push(code);
                }
                else {
                    st.pop();

                    if (st.empty()) {
                        sol++;
                    }
                }
            }
        }

        return sol;
    }
};