STL 큐·스택·문자열 입력의 UB 함정

큐·스택·문자열 입력, 세 문제를 이어서 풀었다. 알고리즘 자체는 셋 다 단순한데 막힌 지점은 전부 알고리즘 밖에 있었다 — 빈 컨테이너에서 front·top·pop을 부르면 미정의 동작(UB, 컴파일러가 어떤 결과를 낼지 보장하지 않는 상태)이라는 것, 그리고 공백이 섞인 입력은 읽는 방식부터 골라야 한다는 것. 이 글에서는 각 문제의 구현을 따라가며 그 두 함정이 어디서 튀어나오는지를 이야기하려 한다. 문제별 풀이 전문은 백준 10845·백준 4949·백준 1152에도 정리돼 있다.

백준 10845 - 큐 (Silver IV)

출처: https://www.acmicpc.net/problem/10845

정수를 저장하는 큐를 만들고 push X, pop, size, empty, front, back 명령을 순서대로 처리하는 문제다. 명령어 수 N은 1~10,000, X는 1~100,000이라 queue<int> STL을 그대로 쓰면 시간은 넉넉하다.

명령어	출력
push 1 / push 2
front	1
back	2
size	2
empty	0
pop	1
pop (비어있을 때)	-1

접근

queue의 기본 인터페이스는 이렇다.

queue<int> q;
q.push(x);    // 큐 뒤에 삽입
q.pop();      // 큐 앞에서 제거 (반환값 없음)
q.front();    // 큐 앞 원소 반환
q.back();     // 큐 뒤 원소 반환
q.size();     // 원소 개수
q.empty();    // 비어있으면 true

여기서 두 가지를 조심해야 했다. 첫째, pop()은 반환값이 없다. 값을 출력하려면 front()로 먼저 읽고 나서 pop()으로 빼는 순서가 필요하다. 둘째, pop/front/back을 빈 큐에서 호출하면 UB라서, 반드시 empty()를 먼저 확인하고 비어 있으면 -1을 출력해야 한다.

작게 재미있었던 건 empty 명령 처리다. q.empty()가 true(1)/false(0)을 반환하는데 이게 문제가 요구하는 출력(비어 있으면 1, 아니면 0)과 정확히 같아서 cout << q.empty()를 그대로 쓸 수 있다. 그리고 스택과 달리 큐는 front()(가장 앞)와 back()(가장 뒤) 두 곳을 조회할 수 있다는 게 스택 문제와의 차이였다.

풀이

명령어 N개를 각각 O(1)로 처리하므로 전체 시간복잡도는 O(N)이다.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    queue<int> q;
    string cmd;

    for (int i = 0; i < n; i++)
    {
        cin >> cmd;

        if (cmd == "push")
        {
            int x;
            cin >> x;
            q.push(x);
        }
        else if (cmd == "pop")
        {
            if (!q.empty())
            {
                cout << q.front() << "\n";
                q.pop();
            }
            else
                cout << -1 << "\n";
        }
        else if (cmd == "size")  { cout << q.size()  << "\n"; }
        else if (cmd == "empty") { cout << q.empty() << "\n"; }
        else if (cmd == "front")
        {
            if (!q.empty()) cout << q.front() << "\n";
            else            cout << -1 << "\n";
        }
        else if (cmd == "back")
        {
            if (!q.empty()) cout << q.back() << "\n";
            else            cout << -1 << "\n";
        }
    }
    return 0;
}

---

백준 4949 - 균형잡힌 세상 (Silver IV)

출처: https://www.acmicpc.net/problem/4949

문자열에서 소괄호 ()와 대괄호 []의 균형이 맞는지 판단해 yes/no를 출력한다. 각 줄은 100자 이하, 영문 알파벳·공백·()·[]로 구성되고 .으로 끝나며, . 한 글자만 있는 줄이 들어오면 입력이 끝난다.

입력	출력
So when I die (the [first] … ).	yes
Half Moon tonight (… no Moon at all].	no
A rope may form )( a trail.	no
([ … ]).	yes
(공백+온점)	yes

접근

괄호가 한 종류라면 여는 괄호에 +1, 닫는 괄호에 -1 하는 balance 카운터로 충분하다. 하지만 이 문제는 두 종류가 섞여 있어서 카운터로는 (] 같은 타입 불일치를 잡을 수 없다. 그래서 stack<char>가 필수다. 이 점이 한 종류만 다루는 9012번과의 결정적 차이다.

규칙은 단순하다. (/[는 push하고, )가 나오면 top이 (일 때만 pop, ]는 top이 [일 때만 pop한다. 조건이 어긋나면 그 자리에서 no다. 여기서도 빈 컨테이너 함정이 나온다 — top()을 빈 스택에서 부르면 UB라서 !st.empty() &&를 반드시 앞에 둬야 한다. 그리고 문자열을 다 돌고 나서 스택에 여는 괄호가 남아 있어도 no다.

stack<char> st;
st.push(c);    // 문자 삽입
st.top();      // 최상단 문자 확인
st.pop();      // 최상단 제거
st.empty();    // 비어있으면 true

입력 처리에도 함정이 있다. 문장에 공백이 포함되므로 cin >>로는 한 줄을 통째로 읽을 수 없다 — cin >>은 공백에서 멈추기 때문이다. getline으로 줄 전체를 읽고, substr로 마지막 .을 떼어낸 뒤 판별한다.

string line;
while (getline(cin, line))   // 공백 포함 한 줄 전체 읽기
{
    if (line == ".") break;
    string s = line.substr(0, line.size() - 1);  // 마지막 '.' 제거
}

풀이

문자열을 한 번 순회하므로 시간복잡도는 O(N)이다.

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

string solution(const string& s)
{
    stack<char> st;

    for (char c : s)
    {
        if (c == '(' || c == '[')
        {
            st.push(c);
        }
        else if (c == ')')
        {
            if (!st.empty() && st.top() == '(')
                st.pop();
            else
                return "no";
        }
        else if (c == ']')
        {
            if (!st.empty() && st.top() == '[')
                st.pop();
            else
                return "no";
        }
    }
    return st.empty() ? "yes" : "no";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    while (getline(cin, line))
    {
        if (line == ".") break;
        string s = line.substr(0, line.size() - 1);
        cout << solution(s) << "\n";
    }
    return 0;
}

---

백준 1152 - 단어의 개수 (Silver V)

출처: https://www.acmicpc.net/problem/1152

영어 대소문자와 공백으로 이루어진 문자열에서 단어 개수를 센다. 단어는 공백 한 개로 구분되고, 문자열이 공백으로 시작하거나 끝날 수 있다. 길이는 최대 1,000,000이고 연속 공백은 없다.

입력	출력
The Curious Case of Benjamin Button	6
(공백)The first character is a blank	6
The last character is a blank(공백)	6

접근 — 진짜 난이도는 입력 처리

알고리즘은 단순 카운터인데 정답률이 33%밖에 안 된다. Silver V라는 난이도표보다, 앞뒤 공백을 어떻게 처리하느냐가 이 문제의 본질이라는 뜻이다. 출제 의도 자체가 알고리즘보다 백준 입력 구조와 cin >> 패턴을 익히라는 쪽에 가깝다.

getline으로 읽으면 앞뒤 공백을 직접 잘라내야(trim) 해서 엣지 케이스에서 틀리기 쉽다. 반면 cin >>는 공백/개행을 자동으로 구분자 삼아 단어 단위로 읽어주니, 앞뒤 공백 문제가 저절로 해결된다.

	cin >> word	getline(cin, line)
공백 처리	자동 skip	공백 포함해서 읽음
앞뒤 공백	자동 무시	직접 trim 필요
EOF 종료	while 조건에서 자동 false	추가 처리 필요
이 문제 적합성	✓ 최적	△ 엣지 케이스 처리 필요

직접 처리한다면 걸리는 엣지 케이스는 이렇다.

• 앞에 공백: ` Hello World` → 공백을 단어로 셀 위험
• 뒤에 공백: Hello World → 마지막 공백 후 빈 단어 카운트 위험
• 공백만 있는 입력: ` ` → 0 출력
• 단어 1개: Hello → 1 출력

종료 조건도 cin >> 쪽이 깔끔하다. while (cin >> word)는 EOF(입력 끝)에 도달하면 자동으로 false가 되어 루프가 끝난다.

string word;
while (cin >> word)   // EOF에서 자동 false → 루프 종료
    answer++;

백준 채점은 입력 파일의 끝이 곧 EOF라 그대로 종료되고, 터미널에서 직접 테스트할 때는 Windows 기준 Ctrl+Z로 EOF 신호를 보낸다.

풀이

문자열 길이만큼 순회하므로 시간복잡도는 O(N)이다.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int answer = 0;
    string word;
    while (cin >> word)
        answer++;
    cout << answer << "\n";
    return 0;
}

---

핵심 요약 — STL 컨테이너 문제의 공통 함정은 빈 컨테이너 접근이 UB라는 것 — top()/front() 전에 empty() 체크가 먼저다. 입력도 마찬가지로 도구 선택이 절반이다: 공백 포함 한 줄은 getline, 단어 단위 + EOF 종료는 while (cin >> word).