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

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

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

---

1) 풀이

처음에는 단순히 '문자열' 문제라고 생각했다...

주어지는 것도 string 이었고 adjacent_find함수를 통해서 짝지어지는 문자의 iterator를 받아서 erase에 넣고

지워주는 코드를 짰다.. 아래가 제일 처음 내가 짰던 코드다.

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

int solution(string s)
{
    int answer = -1;
    
    auto iter=adjacent_find(s.begin(),s.end());
    while(iter!=s.end()){ //짝이 맞는 문자가 없을 때까지
        s.erase(iter-s.begin(),2); //iter-s.begin(): 짝이 맞는 문자 중 첫문자의 인덱스
        iter=adjacent_find(s.begin(),s.end());
    }
    if(s.size()==0) answer=1; //모두 제거 가능
    else answer=0; //모두 제거 불가능
    return answer;
}

정확성 테스트에서의 테스트 케이스는 다 정답으로 처리됐지만,

효율성에서 0점을 맞아버렸다😥

아마도 내가 사용한 함수들이 O(N)이 걸리는 것 같은데, 도무지 시간을 줄일 방법을 못 찾고 있었다.

 

그래서 조금의 구글링을 통해 힌트를 얻고 '아..!' 했다..

기존에 알던 방법인데, 이걸 응용을 못하다니.. 증말 난 응용력이 쓰레기인 것 같다.

2021.03.06 - [알고리즘 | 자료구조/백준] - [백준/c++] 9012 - 괄호

굳이 비교하자면, 위 문제와 풀이가 같다.

 

이 문제는 stack 을 이용하여, string의 문자 하나하나를 push, pop 해서 stack이 비면 

모두 제거 가능(1), 비지 않는다면 제거가 불가능(0)하다고 출력해주면 된다.

바로 직전에 스택에 들어간, 즉 스택의 top과 현재 보고 있는 문자가 같으면 top을 pop해주고,

같지 않거나 스택이 비어있다면 그 문자를 push 해주고 다음 인덱스 문자로 넘어가면 된다.

해당 설명이 코드에 주석으로 달려있으니, 참고바란다!

 

배운 걸 응용하는 힘을 기르자😤

2) 최종 소스코드

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

int solution(string s)
{
    int answer = -1;

    stack<char>st;
    for(int i=0;i<s.size();i++){
        if(!st.empty()&&st.top()==s[i]) st.pop(); //짝이 맞는 경우
        else st.push(s[i]); //스택이 비어있거나 짝이 안 맞는 경우
    }
    if(st.empty()) answer=1; //모두 제거 가능
    else answer=0; //모두 제거 불가능
    return answer;
}

3) 참고자료