단어뒤집기 2(Word Flipping 2)

문제

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(’ ’), 특수 문자(’<’, ’>‘)로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ’<‘와 ’>‘가 문자열에 있는 경우 번갈아가면서 등장하며, ’<‘이 먼저 등장한다. 또, 두 문자의 개수는 같다. 태그는 ’<‘로 시작해서 ’>‘로 끝나는 길이가 3 이상인 부분 문자열이고, ’<‘와 ’>’ 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

출력

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

예제 입력 1

baekjoon online judge

예제 출력 1

noojkeab enilno egduj

예제 입력 2

<open>tag<close>

예제 출력 2

<open>gat<close>

예제 입력 3

<ab cd>ef gh<ij kl>

예제 출력 3

<ab cd>fe hg<ij kl>

예제 입력 4

one1 two2 three3 4fourr 5five 6six

예제 출력 4

1eno 2owt 3eerht rruof4 evif5 xis6

예제 입력 5

<int><max>2147483647<long long><max>9223372036854775807

예제 출력 5

<int><max>7463847412<long long><max>7085774586302733229

예제 입력 6

<problem>17413<is hardest>problem ever<end>

예제 출력 6

<problem>31471<is hardest>melborp reve<end>

예제 입력 7

<   space   >space space space<    spa   c e>

예제 출력 7

<   space   >ecaps ecaps ecaps<    spa   c e>

풀이

이 문제는 일반적인 문자열 전체 뒤집기가 아니다. 태그 내부는 그대로, 태그 밖에서는 공백이나 태그 경계로 끝나는 단어만 뒤집는다. 왼쪽부터 한 글자씩 읽으면서 태그 밖 글자는 스택에 모으고, 단어가 끝나는 순간 꺼내 출력하면 순서가 반대가 된다.

<ab cd>ef gh<ij kl>을 따라가면 첫 <에서 비어 있는 스택을 출력하고 태그 상태로 들어간다. <ab cd>는 공백까지 그대로 쓴다. ef는 태그 밖이므로 스택에 쌓였다가 공백에서 fe로 나온다. gh는 다음 <에서 hg로 출력한다. 마지막 <ij kl>은 다시 그대로다. 태그 안의 공백에서는 스택을 비우지 않아야 한다.

코드의 print는 스택에 쌓인 현재 단어를 모두 꺼내 출력한다. <와 태그 밖 공백에서 호출하고, 입력이 끝난 뒤에도 한 번 호출해 마지막 단어를 빠뜨리지 않는다. 태그 안에서는 <와 >를 포함한 모든 문자를 즉시 출력한다. 문자열 길이를 L이라 할 때 각 문자는 한 번 쌓이거나 출력되므로 시간 O(L), 최대 단어 길이만큼 스택 공간 O(L)이다. 태그만 연속한 <int><max>나 숫자가 섞인 one1을 확인하면 경계 처리를 검증할 수 있다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


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

    public static void replace() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String s = in.readLine();

        boolean tag = false;
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '<':
                    print(out, stack);
                    out.write(ch);
                    tag = true; // 괄호시작
                    break;
                case '>':
                    out.write(ch);
                    tag = false; //괄호 종료
                    break;
                default:
                    if (tag) {
                        out.write(ch);
                    } else if (ch == ' ') {
                        print(out, stack);
                        out.write(ch);
                    } else {
                        stack.push(ch);
                    }
                    break;
            }
        }
        print(out, stack);
        out.write('\n');
        out.flush();
        out.close();
        in.close();
    }

    public static void print(BufferedWriter out, Stack<Character> stack) throws Exception {
        while(!stack.isEmpty()) {
            out.write(stack.pop());
        }
    }
}

문제 사이트 : https://www.acmicpc.net/problem/17413