짝지어 제거하기

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 (programmers.co.kr)

1. 문제이해

1.1. 문제 출제 의도 파악하기

• 문제를 효율적으로 해결하기 위한 최적 자료구조를 결정할 수 있는지 물어보는 문제입니다.
• 직관적인 방법을 사용할 경우 이 문제는 $O(n^2)$이 소요되지만, 적절한 자료구조를 사용한다면 $O(n)$만 소요됩니다.

1.2. 문제 해결하기

1. O(n²) 알고리즘

• 같은 알파벳이 2개 붙어있을 때, 그 둘을 제거하고 다시 처음부터 검사를 해야만 합니다.
• 문자열의 길이가 1,000,000이므로 $O(n^2)$ 알고리즘을 사용하는 것은 위험합니다.

2. O(n) 알고리즘

• Stack을 사용하면 연속해서 같은 알파벳이 나오는 경우 처리가 가능하고 처음부터 검사할 필요도 없습니다.
• 
  1. b를 stack에 넣습니다.
  2. a는 stack의 top인 b와 다르므로 stack에 넣습니다.
  3. a는 stack의 top인 a와 같으므로 pop()을 해줘서 제거합니다.
  4. b는 stack의 top인 b와 같으므로 pop()을 해줘서 제거합니다.
  5. a를 stack에 넣습니다.
  6. a는 stack의 top인 a와 같으므로 pop()을 해줘서 제거합니다.
  7. 모든 문자를 탐색했을 때, stack이 비어있다면 1을, 비어있지 않다면 0을 반환합니다.
     이는 stack.empty()와 같습니다.

2. 문제풀이

2.1. 전체코드

#include <stack>
using namespace std;

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