[C++로 풀이] 짝지어 제거하기⭐⭐

📌 짝지어 제거하기

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

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

문자열의 길이가 1,000,000 백만까지 갈 수 있으므로 웬만하면 O(N) 로 푸는게 좋을 것 같다. O(N^2) 으로 가면 시간 초과가 날 것이다.

짝을 짓는데에는 ✨스택✨이 최고인듯 하다.. 스택에 짝을 찾지 못한 것만 삽입한다. 짝을 찾았다는 것은 스택의 가장 위에 있는 것(가장 최근 것)과 같은 것을 찾았다는 것이므로 이를 스택에서 제거한다. 최종적으로 s 순회를 마쳤을 때 스택이 비어있다면 전부 짝을 찾아서 스택을 나간 것이므로 1 을 리턴하고, 스택이 비어있지 않다면 짝을 못 찾은게 있다는 것이므로 0 을 리턴한다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기