17413번: 단어 뒤집기 2

문제

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 합니다. 단어는 알파벳 소문자와 숫자로 이루어져 있으며, 단어와 단어 사이는 공백으로 구분됩니다. 단, <와 >로 둘러싸인 부분은 '태그'로 간주하여 내부의 문자를 뒤집지 않고 원래 순서대로 출력해야 합니다.

• 입력: 첫째 줄에 문자열 S가 주어집니다. (길이 100,000 이하)
• 출력: 첫째 줄에 문제의 규칙에 맞게 단어를 뒤집어서 출력합니다.

링크: https://www.acmicpc.net/problem/17413

풀이: Stack과 상태 플래그(Flag)를 이용한 분기 처리

단어를 뒤집을 때는 후입선출(LIFO) 자료구조인 Stack을 사용하는 것이 정석입니다. 태그 내부인지 외부인지를 판별하는 flag 변수를 두고, 각 문자를 순회하며 조건에 맞게 분기 처리합니다.

• 상태 관리:
  • 태그의 시작인 <를 만나면: 여태까지 스택에 쌓아둔 단어를 모두 꺼내어 뒤집어 출력한 뒤, flag를 true로 바꿉니다.
  • 태그의 끝인 >를 만나면: flag를 false로 되돌리고 >를 출력합니다.
• 문자 처리:
  • flag == true 인 경우: 태그 내부이므로 스택에 넣지 않고 그대로 출력합니다.
  • flag == false 이고 공백( )인 경우: 단어가 끝난 것이므로 스택의 문자를 모두 꺼내 출력하고, 공백 자체도 출력합니다.
  • 그 외의 일반 문자인 경우: 단어의 일부이므로 나중에 뒤집기 위해 스택에 push 합니다.
• 잔여 처리:
  • 반복문이 끝난 후 스택에 남아있는 문자가 있다면 모두 꺼내어 출력해 줍니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       String s = br.readLine();

       Stack<Character> st = new Stack<>();
       boolean flag = false; // 태그 안인지 밖인지 판별하는 플래그
       
       for (char c : s.toCharArray()) {
          // 1. 태그가 시작되는 경우
          if (c == '<') {
             // 기존에 스택에 쌓여있던 단어를 모두 뒤집어서 출력
             while (!st.isEmpty()) {
                bw.write(st.pop());
             }
             flag = true;
             bw.write(c);
          } 
          // 2. 태그가 끝나는 경우
          else if (c == '>') {
             flag = false;
             bw.write(c);
          } 
          // 3. 태그 내부인 경우 (그대로 출력)
          else if (flag) {
             bw.write(c);
          } 
          // 4. 태그 외부이면서 공백을 만난 경우 (단어의 끝)
          else if (c == ' ') {
             // 스택에 쌓인 단어를 뒤집어 출력하고 공백 출력
             while (!st.isEmpty()) {
                bw.write(st.pop());
             }
             bw.write(c);
          } 
          // 5. 태그 외부의 일반 문자인 경우 (스택에 적재)
          else {
             st.push(c);
          }
       }

       // 마지막으로 스택에 남아있는 문자들 모두 출력
       while (!st.isEmpty()) {
          bw.write(st.pop());
       }

       bw.flush();
    }
}

알고리즘 분류

자료 구조 (Data Structures), 문자열 (String), 스택 (Stack)