짝지어 제거하기

문제 링크

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

코딩테스트 연습 - 짝지어 제거하기

 

문제 풀이 코드

 

1. 첫번째 코드 (실패)

원래 이런식으로 string의 erase 함수를 써서 풀려고 했다.

테스트 케이스는 모두 통과했으나.. 효율성이 나가리 

자세히 살펴보니 시간복잡도가 O(N^2)이다.

 

그래서 스택을 써야함을 깨달았고 아래는 2번째 시도한 정답 코드다.

 

2. 두번째 코드 (성공)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int solution(string s)
{
    int answer = -1;
    
    vector <char> v;
    
    for(int i=0; i<s.length(); i++){
        v.push_back(s[i]);
        if(v.size()>=2){
            if(v[v.size()-1]==v[v.size()-2]){
                v.pop_back();
                v.pop_back();
            }
        }
    }
    
    if(v.empty()) answer=1;
    else answer=0;
    
    return answer;
}

증맬루.. 간단한 문젠데 왜 난 항상 한번에 해결하지 못하는 것인가...

심지어 인형뽑기 문제랑 똑같은 유형.. 바로 전에 풀어놓고서;;

좀 더 열심해 해야겠다 하ㅏ하