[BaekJoon-9093] 단어 뒤집기

문제

문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 공백이 하나 있다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문장의 단어를 모두 뒤집어 출력한다.

예제 입력 1

2
I am happy today
We want to win the first prize

예제 출력 1

I ma yppah yadot
eW tnaw ot niw eht tsrif ezirp

풀이

스택을 이용하면 N개의 문자를 스택에 넣었다 빼면 역순으로 출력할 수 있다.

스택에 알파벳을 넣는다.
공백이나 문자열의 끝이면 스택에서 모두 빼낸다.
역순으로 만들도록 출력

단어의 경계에서만 스택 비우기

단어를 읽는 동안 문자를 스택에 넣었다가 공백을 만나면 전부 꺼낸다. 나중에 들어간 문자가 먼저 나와 단어 안의 문자 순서만 뒤집힌다. 예를 들어 I am happy에서 I는 그대로, am은 ma, happy는 yppah가 된다. 공백 자체는 원래 위치에 출력하므로 단어 순서는 바뀌지 않는다.

마지막 단어 뒤에는 실제 공백이 없으므로, 코드는 입력 한 줄 끝에 개행 문자를 붙여 마지막 스택을 비우는 신호로 쓴다. 마지막 경계를 빠뜨리면 마지막 단어가 아예 출력되지 않는다. 단어가 한 글자여도 같은 규칙이 작동하고, 테스트 케이스마다 새 스택을 사용한다.

문장 길이를 L이라 하면 각 문자는 스택에 한 번 들어가고 한 번 나오므로 O(L) 시간이다. 스택에 동시에 들어 있는 것은 현재 단어뿐이라 추가 공간은 최대 단어 길이만큼이다. 코드에서는 줄마다 flush하지만 큰 입력에서 출력 호출을 줄이려면 여러 결과를 버퍼에 모아 마지막에 쓰는 방법도 있다.

읽은 문자	스택 아래→위	출력
a	a	빈 문자열
m	a, m	빈 문자열
공백	비움	ma와 공백
문장 끝	비움	마지막 단어의 역순과 개행

스택을 문장 전체에 대해 한 번만 비우면 단어 순서까지 뒤집힌다. 이 문제는 단어마다 독립적으로 순서를 바꾸므로 공백을 만날 때마다 비워야 한다. 입력에는 단어 사이 공백 하나가 보장되어 있어 연속 공백의 별도 규칙은 필요 없다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        flipWord();
    }

    public static void flipWord() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = parseInt(in.readLine());

        while (0 < t--) {
            Stack<Character> stack = new Stack<>();
            String word = in.readLine() + "\n";
            for (int i  = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (ch != ' ' && ch != '\n') {
                    stack.push(ch);
                    continue;
                }
                while(!stack.isEmpty()) {
                    out.write(stack.pop());
                }
                out.write(ch);
            }
            out.flush();
        }
        out.close();;
        in.close();;
    }
    

    public static int parseInt(String arg) {
        return Integer.parseInt(arg);
    }
}