[프로그래머스] 짝지어 제거하기 / stack(LIFO)

문제

 

풀이 1

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

int solution(string s)
{
	int answer = 0, i = 0;
	while (i < s.length()) {
		if (s[i] == s[i + 1]) {
			s.erase(i, 2);
			i = 0;
		}
		else i++;
		if (s.length() == 0) return 1;
	}
	return 0;
}

while문으로 푼 풀이이다. 정답은 다 맞혔으나 효율성 테스트를 전혀 통과할 수 없었다.
알파벳이 2개인 짝을 제거할 경우 다시 처음부터 탐색하기 때문에 비효율적일수밖에 없었을 것이다.

 

 

풀이 2

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

int solution(string s)
{
    stack<int> st;
    for(int i=0; i<s.length(); i++){
        if(!st.empty() && st.top() == s[i]){
            st.pop();
        }
        else st.push(s[i]);
    }
    return st.empty()?1:0;
}

stack을 사용하면 시간복잡도 O(n)으로 문제를 해결할 수 있다.

 

스택(Stack)의 멤버함수 정리

멤버함수	기능
s.push(element)	top에 원소를 추가한다
s.pop()	top에 있는 원소를 삭제한다
s.top()	top에 있는 원소를 반환한다. (stack에서는 가장 최근에 들어온 원소가 top에 위치한다.)
s.empty()	스택이 비어있으면 true를, 그렇지 않다면 false를 반환한다.
s.size()	스택의 사이즈를 반환한다.
s.swap(stack1, stack2)	두 스택의 내용을 바꿔준다.

 

 

---

다른 사람 풀이

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

using namespace std;



int solution(string s)
{
    stack<char> c;
    int answer = 0;
    for(int i=0; i<s.size(); i++){
        if(c.size()==0){
            c.push(s[i]);
            continue;
        }
        if(c.top() == s[i])
        {
            c.pop();
        }
        else{
            c.push(s[i]);   
        }
    }
    if(c.empty())
        answer = 1;
    else{
        answer = 0;
    }

    return answer;
}

 

 

---

https://twpower.github.io/75-how-to-use-stack-in-cpp

[C++] C++ STL stack 기본 사용법과 예제