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

문제 링크

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

프로그래머스

 

프로그래머스 레벨2문제는 풀다보면 느끼는건데 너무 쉽게 생각하면 또랑에 빠져서 다시 고치고 어렵게 생각하면 쉬운문제라 항상 당황하는것 같습니다.

 

코드 및 풀이

오답 코드(효율성 0점)

/*

짝지어 제거하기 -> 같은 알파벳 2개 붙어 있는 짝을 찾음 그 둘을 제거한 뒤 이어 붙임

성공할 수 있으면 1 없으면 0

음.. 반복문을 전체를 도는것은 에바니 index기준을 기억해뒀다가 제거됐을때 이어졌는지 확인을 하고

그 다음에 이어서 진행하면 될듯?

ababababba 이렇게 있으면 abababa bb a 인데 bb를 제거하고 나서 aa를 확인하는 방식으로?

*/

#include <iostream>

#include<string>

using namespace std;

int solution(string s)

{

    int answer = -1;

    int idx = 0;

   

    while(1){

        if(idx == s.length() - 1)

            break;

        if(s[idx] == s[idx + 1]){

            s.erase(s.begin() + idx , s.begin() + idx + 2); // (first,last] 즉 i+2는 지우지 않고 i,i+1만 제거

            idx --;

            continue;

        }

       

        idx++;

    }

   

    if(s.length() == 0)

        answer = 1;

    else

        answer = 0;

    return answer;

}

너무 간단하게 얕봤다..ㅋㅋㅋㅋㅋ 이런식으로하면 시간복잡도가 너무 높아져 무조건 틀려버리게 됩니다.

정답 코드

/*

다 맞는데 효율성 모두 시간초과?

해결 과정 적어놓자

abccba라면 원래 코드의 형태라면 생각을 해보니 abc 후에 c가 들어올때 cc 이탈 bb이탈 aa이탈 하면 바로 끝내는 식으로 하면 어떨까?

스택을 사용하면 될듯?

비어있으면 비교할 대상이 없으니 일단 stack에 넣고 비어있지 않으면 비교 비교했는데 다르면 push

stack의 top과 비교해서 같으면 pop을 하면서 나중에 stack이 비어있으면 1return 아니면 0리턴으로

*/

#include <iostream>

#include<string>

#include<stack>

using namespace std;

int solution(string s)

{

    int answer = -1;

    stack<char> stack;

   

    for(int i = 0; i < s.length();i++){

        char c = s[i];

       

        if (stack.empty())

            stack.push(c);

        else{

            if(stack.top() == c)

                stack.pop();

            else{

                stack.push(c);

            }

        }

    }

   

    if(stack.empty())

        return 1;

    else

        return 0;

}

스택을 이용하여 같게 된다면 pop을하고 아니라면 push를 진행하였습니다. 

 

스택이 비어있다는 것은 비교할 대상이 아직 없다는 것이니 그것 또한 push하였습니다.