프로그래머스 12973 - 짝지어 제거하기

오답 (55.8 / 100)

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

using namespace std;

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

    return stk.empty() ? 1 : 0;
}

⚠️ 에러

• signal: segmentation fault (core dumped)

💥 원인

• stack이 비어있는 상태에서 stk.top()을 한 경우 Undefinded behavior이기 떄문에 위와 같은 에러 발생

🤔 시도

• 현재 조건문 뒤에 && !stk.empty() 추가
• 조건문은 순서대로 실행되기 때문에 empty() 검사를 먼저 하지 않아서 에러 안 고쳐짐

❓ 의문
근데 맨 처음에 항상 stack이 비어있는 상태로 stk.top()을 호출하는데 테스트 케이스 통과가 왜 된 거지

• undefined behavior는 “항상” 크래시가 나는 건 아님
• 어떤 환경에서는 스택이 empty일 때 top()이 운 좋게 메모리 어딘가를 참조해도 즉시 크래시가 안 나고, 그 쓰레기 값이 s[i]와 같지 않아 else문으로 넘어가면서 이후 로직이 정상처럼 동작하기도 함
• 반대로 어떤 환경(디버그 모드, 다른 STL 구현, 런타임 검증 켜짐 등)에서는 즉시 assert/크래시가 날 수 있음

정답

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

using namespace std;

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

    return stk.empty() ? 1 : 0;
}