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

---

Programmers - [2017 팁스타운] 짝지어 제거하기

---

사용 언어 - C++

소요 시간 - 약 30분

정답 여부 - O

---

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12973

---

문제 요약

1. 주어진 문자열에서 연속되는 두 문자를 제거
2. 반복
3. 문자열에 아무것도 남지 않으면 1, 남아있다면 0 return

---

최종 코드

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

using namespace std;

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

    return 0;
}

---

트러블 슈팅

1. 처음에는 문자열에서 첫번째와 두번째, 두번째와 세번째를 비교하며 같다면 erase로 지우는 식을 선택 -> 효율성 면에서 매우 떨어짐 -> 지워질 때마다 0번 인덱스로 돌아가 처음부터 다시 비교를 해야하기 때문 -> 시간복잡도 O(N^2)

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

int solution(string s)
{
    int answer = 0;

    //1번과 2번을 비교, 2번과 3번을 비교 ...
    for(int i = 0; i < s.size() - 1;)
    {
        if(s.size() < 2) break;
        
        if(s[i] == s[i + 1])
        {
            s.erase(s.begin() + (i + 1));
            s.erase(s.begin() + i);
            
            i = 0;
            continue;
        }
        
        i++;
    }
    
    if(s.empty()) answer = 1;

    return answer;
}

---

문제 풀이 후 소감

• 처음으로 효율성 체크가 있는 문제를 풀어봤다. 처음 제출했던 코드도 틀린 답은 아니었지만, 효율성 문제에서 0점이 나온 것을 보고 앞으로 문제를 풀 떄 코드가 효율적인지를 조금 더 생각해봐야겠다

• coding-test