[프로그래머스 C++] 짝지어 제거하기

 

[프로그래머스 C++] 짝지어 제거하기

 

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

프로그래머스

---

 

 

해결전략

 

문자열

 

 

---

 

첫 풀이 - 실행 통과, 효율성 테스트 시간 초과

 

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

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

    while (!s.empty())
    {
        temp.clear();

        //연속된 문자를 찾은 다음 뺀다
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == s[i + 1] && i < s.size() - 1)//인덱스 범위 초과 체크
            {
                i++;//중복 문자를 건너뛰기 위해 인덱스 증가
                //for문 마지막에 i++이 있으므로 i++이 두번 일어날 것이다. 인덱스는 2증가하므로 문자 2개를 지나친다.
            }
            else
            {
                temp += s[i];//temp에 중복되지 않은 문자들 추가
            }
        }

        //문자가 더 이상 삭제되지 않을때
        if (s.size() == temp.size())
            break; //while 루프를 빠져나온다.


        s = temp;//s 문자열을 temp로 바꿔준다.
    }


    //모든 문자가 삭제되었으면 1, 남은 문자가 있으면 0
    answer = s.empty() ? 1 : 0;

    return answer;
}

 

 

---

 

 

정답 코드

 

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int solution(string s) {
    
    int answer = -1;
    
    stack<char> st; // 중복되지 않은 문자를 저장하기 위한 스택

    for (int i = 0; i < s.size(); ++i) 
    {
        if (st.empty()) { // 스택이 비어있으면 문자 추가
            st.push(s[i]);
            continue;
        }
        
        if (st.top() == s[i]) { // 스택의 top이 현재 문자와 같으면 스택에서 삭제
            st.pop();
        }
        else { // 스택의 top과 현재 문자가 다른 경우 스택에 추가
            st.push(s[i]);
        }
    }
    
     // 스택 비어있으면 1, 그렇지 않으면 0 반환
    answer = st.empty() ? 1 : 0;
    
    return answer;
}

 

 

---