프로그래머스, C++) Lv 2. 짝지어 제거하기

문제

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

 

 

 

기존 코드

#include <iostream>

#include <string>

using namespace std;

// 앞에 붙은 글자 제거

int solution(string s)

{

    int answer = 0;

   

    int pos = 0;

    while(pos != s.size())

    {

        if(s=="")

        {

            answer = 1;

            break;

        }

       

        if(s[pos] == s[pos+1])

        {

            s.erase(pos,2);

            pos -=1;

        }

        else

            ++pos;

    }

   

    return answer;

}

 

문제점

• 정확도는 잘 맞는다. 그러나 효율성에서 모두 실패함. 
  • 그래서 틀렸다고 나옴. erase와 pos쪽이 문제가 되었음

 

• erase를 사용해 원본을 제거
  • 지울 때 마다, O(n)번의 시간복잡도로 계산됨. (shift 발생으로 인해 연산량이 많아진다.)
  •  pos에 관해서 위치에 관한 제약조건이 추가된다

---

수정본

• Stack을 사용해 풀면 해결
• 다시 반복을 하지 않아도 되고, 위치에 대해서도 제약 조건이 필요없음.

#include <iostream>

#include <string>

using namespace std;

// 앞에 붙은 글자 제거

int solution(string s)

{

    string tmp;

    int answer = 0;

   

    for(char c : s)

    {

        if(!tmp.empty() && tmp.back() == c)

        {

            tmp.pop_back();

        }

        else

            tmp.push_back(c);

    }

    if(tmp.empty()) answer = 1;

   

    return answer;

}