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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12973

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

 

짝지어 있는 문자를 제거할 때, 모든 문자를 제거할 수 있는지 여부를 확인하여 출력하는 문제입니다.

문자열의 길이는 최대 100만이고, 여러 번 검사해야 할 수도 있기 때문에 시간복잡도를 고려해서 짜야 합니다.

 

제가 생각한 방법입니다.

stack 자료구조를 이용해서 해결하며, 아래와 같은 과정을 거칩니다.

• stack의 맨 위의 문자와, 문자열의 순서에 맞는 문자를 비교합니다.
• 둘이 같은 경우, stack의 문자를 제거합니다.
• 둘이 다른 경우, stack에 문자를 추가합니다.

맨 처음 stack이 비었을 때도 고려해야 합니다.

 

코드 링크: GitHub

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

int solution(string input) {
    
    stack<char> s;
    for (int i = 0; i < input.size(); i++) {
        if (s.empty()) {
            s.push(input[i]);
        }
        else {
            if (input[i] == s.top()) {
                s.pop();
            }
            else {
                s.push(input[i]);
            }
        }
    }

    if (s.empty()) return 1;
    else return 0;

}

 

stack을 떠올리면 쉽게 풀 수 있지만, 그렇지 못하면 구현에 어려움을 겪을 수 있는 문제라고 생각합니다.