[2017 팁스타운] 짝지어 제거하기 C++

https://programmers.co.kr/learn/courses/30/lessons/12973

코딩테스트 연습 - 짝지어 제거하기

- Stack사용/ 예시문자열 "baabaa"

1) 문장의 첫 문자(s[0]) push

2) 두번째 문자(s[1])부터 s.size만큼 반복하며 stack의 top과 비교

3) top과 비교문자가 같으면 pop

4) top과 비교문자가 다르면 push

5) 반복문 종료전 stack이 empty인 경우 비교하지 않고, push만 실행

6) 반복문 종료후 stack이 empty인지 확인

 

---

PASS) stack 사용하여 top과 다음 비교문자가 같으면 pop/ 다르면 push, 정확성: 60.2/ 효율성: 39.8

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = -1;

    bool flag = 0;

    stack<char> st;
    st.push(s[0]);
    for (int i = 1; i < s.size(); i++) {
        if (st.empty()) {
            st.push(s[i]);
            continue;
        }

        char ch = st.top();
        if (ch == s[i]) 
            st.pop();
        else
            st.push(s[i]);
    }

    if (st.empty())
        answer = 1;
    else
        answer = 0;

    return answer;
}

 

FAIL) substr로 2글자씩 split하여 비교, 정확성: 60.2 /효율성: 0.0

#include <iostream>
#include<string>
using namespace std;

int solution(string s)
{
    int answer = -1;

    bool flag = 0;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s.empty()) {
            flag = 1;
            break;
        }
        
        string tmp = s.substr(i, 2);

        if (tmp[0] == tmp[1]) {
            s.erase(i, 2);
            i = -1;
        }
    }
    
    if (flag==1)
        answer = 1;
    else 
        answer = 0;

    return answer;
}