TIL 2026-04-09

2026-04-09 알고리즘 백준 과제

목차

• 백준 10845 - 큐 (Silver IV)
• 백준 4949 - 균형잡힌 세상 (Silver IV)
• 백준 1152 - 단어의 개수 (Silver V)

---

백준 10845 - 큐 (Silver IV)

🔗 https://www.acmicpc.net/problem/10845

---

문제 분석

문제 요약

정수를 저장하는 큐를 구현하고, 입력으로 주어지는 명령을 처리하는 프로그램.

push X, pop, size, empty, front, back 명령어를 순서대로 처리하고 결과를 출력.

제한사항

• 명령어 수 N: 1 이상 10,000 이하
• push X에서 X: 1 이상 100,000 이하

입출력 예

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

핵심 포인트

• queue<int> STL 컨테이너 사용
• pop / front / back: 빈 큐에서 호출 시 UB → empty() 체크 후 -1 출력
• empty 명령어: 비어있으면 1, 아니면 0
• 스택과 달리 front()(앞)과 back()(뒤) 두 가지 조회 존재

---

헤더 라이브러리

#include <queue>

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

• pop()은 반환값이 없음 → 값 확인은 front() 후 pop() 순서

---

코드 풀이

풀이 — queue<int> 활용

시간복잡도: O(N) — 명령어 N개 각각 O(1) 처리

#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;
}

복기

• pop()은 반환값 없음 → 값을 읽으려면 front() 먼저, 그다음 pop()
• pop / front / back 모두 빈 큐에서 호출 시 UB → empty() 체크 필수
• empty() 반환값: true(1) / false(0) — empty 명령어 출력과 동일해 cout << q.empty() 가능
• 스택과 달리 큐는 front()(가장 앞)과 back()(가장 뒤) 두 곳 조회

---

백준 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

핵심 포인트

• 두 종류 괄호가 섞이므로 balance 카운터 방식 불가 → stack<char> 필수
• ( / [ → push, ) → top이 (이면 pop, ] → top이 [이면 pop
• top 확인 전 반드시 empty() 체크 → 비어있으면 즉시 "no"
• 루프 종료 후 스택에 남은 괄호 있으면 "no"
• getline으로 한 줄씩 읽고 마지막 "." 제거 후 판별

---

헤더 라이브러리

#include <stack>

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

getline vs cin >>

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

• cin >>은 공백에서 멈춰 다음 원소를 읽음 → 공백 포함 입력은 반드시 getline 사용

---

코드 풀이

풀이 — stack<char> 활용

시간복잡도: 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;
}

복기

• 두 종류 괄호 → stack<char> 필수 (balance 카운터로는 타입 구분 불가)
• ) 닫힐 때 top이 [면 즉시 "no" — 타입 불일치 처리
• !st.empty() && 선행 체크 없이 top() 호출 시 UB → 반드시 선행
• 루프 후 st.empty() — 여는 괄호가 남았는지 최종 확인
• 9012와의 차이: 종류가 2개라 stack 방식만 가능, balance 카운터 불가
• getline 사용 이유: 입력에 공백이 포함되어 cin >> 로 한 줄 전체를 읽을 수 없음

---

백준 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%의 진짜 난이도는 입력 처리
• 앞뒤 공백을 어떻게 처리하느냐가 핵심 → cin >> 가 공백/개행을 자동 skip
• while (cin >> word) 패턴: EOF 도달 시 자동 false → 별도 종료 조건 불필요
• getline 으로 읽으면 앞뒤 공백을 직접 처리해야 해서 엣지 케이스에서 틀리기 쉬움

---

입력 구조 파악 — 이 문제의 진짜 의도

cin >> vs getline 비교

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

엣지 케이스 (Edge Case)

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

---

헤더 라이브러리

cin >> EOF 패턴

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

• 백준 채점 시: 입력 파일 끝 = EOF → 자동 종료
• 터미널 직접 입력 시: Ctrl+Z (Windows) → EOF 신호

---

코드 풀이

풀이 — cin » 활용

시간복잡도: 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;
}

복기

• Silver V지만 정답률 33% — 알고리즘이 아닌 입력 처리가 난이도의 본질
• cin >> 는 공백/개행을 자동으로 구분자로 처리 → 앞뒤 공백 엣지 케이스 자동 해결
• while (cin >> word) 패턴으로 EOF 처리 → 별도 종료 조건 불필요
• 이 문제의 의도: 알고리즘보다 백준 입력 구조와 cin >> 패턴 숙지