코딩테스트/프로그래머스
[레벨 2] 짝지어 제거하기
marmelo12
2021. 12. 8. 11:33
반응형
#include <iostream>
#include<string>
using namespace std;
int solution(string s)
{
int len = s.size();
if (len % 2 == 1)
return 0;
else if (len <= 1)
return 0;
string::iterator it = s.begin();
while (true)
{
if (it == s.end())
break;
if (*it == *(it + 1))
{
s.erase(it, it + 2);
it = s.begin();
}
else
++it;
}
if (s.size() > 0)
return 0;
return 1;
}
위 방식은 처음부터 순회하면서 현재문자와 다음문자가 같다면 지운다음 다시 처음부터 반복하는 코드.
정답은 맞지만 효율성에서 실패가 뜬다. -> O(N^2)에 가까운 코드
조금 고민을 해보고 다른 사람의 풀이를 보았음. 스택을 이용하여 하나씩 담아보면서 다음 문자열에 들어올 문자가 스택의 top과 같다면 pop하는 형식으로 해결.
#include <iostream>
#include<string>
#include<stack>
using namespace std;
int solution(string s)
{
int len = s.size();
if (len % 2 == 1)
return 0;
else if (len <= 1)
return 0;
stack<char> st;
for(int i = 0; i < len; ++i)
{
if(st.size() > 0 && st.top() == s[i])
st.pop();
else
st.push(s[i]);
}
if(st.size() > 0)
return 0;
return 1;
}
반응형