BOJ 9093. 단어 뒤집기

게시 2020/04/07 수정 2026/10/07 작성자 August

조회 7 분 읽는 시간

문제링크 : https://www.acmicpc.net/problem/9093

문제 요약

여러 줄의 문장을 받아 각 단어 안의 글자 순서만 거꾸로 바꾸고 단어 사이의 순서와 공백은 그대로 두는 문제다. 첫 줄에 테스트 케이스 수가 오고, 이후 한 줄에 문장 하나씩 주어진다. 문장 길이는 최대 1,000, 단어 길이는 최대 20이며 단어 사이에는 공백이 하나씩 있다.

1. 문제 해석

스택은 데이터를 넣을 때와 꺼낼 때 역순으로 꺼내진다. 예를 들어, C, B, A 순으로 데이터가 삽입되었다면, 하나씩 Pop하여 출력해보면 A, B, C가 출력될 것이다.

단어 뒤집기 문제도 이러한 스택의 성질을 이용하면 쉽게 해결할 수 있다. I am happy today 라는 문자열이 주어졌다면 I ma yppah yadot로 출력될 것이다. 먼저, I가 스택에 들어간다. -> 공백문자가 들어온다. -> 스택을 비워주면서 출력한다. (I가 출력) -> a가 스택에 들어간다. -> m이 스택에 들어간다. -> 공백문자가 들어온다. -> 스택을 비워주면서 출력한다. (ma가 출력) -> … 이렇게 계속 반복하다 보면 단어를 뒤집어서 출력할 수 있다.

왜 이 방법이 맞는가

공백은 단어의 경계다. 공백을 만날 때까지 넣은 글자들은 정확히 한 단어이고, 스택은 마지막에 넣은 글자를 먼저 꺼내므로 그 단어가 뒤집혀 나온다. 스택을 비운 뒤에 공백을 그대로 출력하므로 단어 사이의 순서와 공백 위치도 유지된다.

남는 문제는 마지막 단어다. 마지막 단어 뒤에는 공백이 없어서, 공백을 만날 때만 스택을 비우면 마지막 단어가 스택에 남은 채로 끝난다. 아래 코드는 문장 끝에 개행 문자 '\n'을 직접 붙이고, 공백과 개행을 모두 “단어의 끝”으로 취급해서 이 문제를 해결한다. 이렇게 경계 처리를 위해 끝에 덧붙이는 값을 보초(sentinel)라고 부른다.

2. 문제 풀이

  
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); // 입출력 속도 향상 
    int t; cin >> t;
    cin.ignore(); // 개행 문자가 없어서 getline()이 문자열을 못받는경우 방지 
    while (t--) {
        string str;
        getline(cin, str);
        str += '\n';
        stack<char> s;
        for (char ch : str) {
            if (ch == ' ' || ch == '\n') { // 공백이거나 개행문자이면 
                while (!s.empty()) { // 스택을 전부 비워주면서 출력 
                    cout << s.top();  
                    s.pop();
                }
                cout << ch;
            } else { // 공백이나 개행문자가 아니면 스택에 차곡차곡 담아준다. 
                s.push(ch);
            }
        }
    }
    return 0;
}

코드 읽기

cin >> t는 숫자만 읽고 그 뒤의 줄바꿈 문자를 입력 버퍼에 남겨 둔다. 이 상태로 바로 getline을 부르면 남아 있던 줄바꿈까지만 읽어서 빈 문자열을 받는다. cin.ignore()가 그 줄바꿈 한 글자를 버려서 첫 문장을 제대로 읽게 한다.
getline은 줄 끝의 개행 문자를 버리고 돌려준다. 그래서 str += '\n'으로 보초를 다시 붙인다. 이 개행은 마지막 단어를 비우는 신호이면서, 출력에서 줄을 바꾸는 역할도 함께 한다.
반복문 안에서는 글자를 스택에 쌓다가, 공백이나 개행을 만나면 스택이 빌 때까지 꺼내 출력한 뒤 그 구분 문자를 출력한다.
스택은 테스트 케이스마다 새로 만들어지므로 이전 문장의 글자가 남지 않는다.

복잡도

문장 길이를 L이라고 하면, 각 글자는 스택에 한 번 들어가고 한 번 나온다. 따라서 문장 하나당 시간은 O(L)이고, 스택에는 최대 단어 길이만큼만 쌓이므로 추가 공간은 O(단어 길이)다. 문장이 최대 1,000자이므로 테스트 케이스가 많아도 넉넉하다.

스택 없이 풀 수도 있다

스택은 “뒤집기”를 자연스럽게 표현하는 도구일 뿐, 꼭 필요하지는 않다. 단어의 시작 위치를 기억해 두었다가 공백을 만나면 그 구간을 std::reverse로 뒤집어도 같은 결과가 나온다. 시간 복잡도는 같고, 문자열 안에서 바로 뒤집으므로 별도의 스택이 필요 없다. 이 문제를 스택으로 푸는 의미는 LIFO(후입선출) 성질이 뒤집기와 같다는 점을 익히는 데 있다. 태그와 공백 규칙이 추가된 확장 문제로 BOJ 17413. 단어 뒤집기 2가 있다.

ProblemSolving, BOJ