[백준] 9093번: 단어 뒤집기

💡문제 분석 요약

주어진 문장을 단어의 순서는 바꾸지 않고 단어를 모두 뒤집어서 출력하는 문제이다.

 

💡알고리즘 설계

• 한 문장씩 입력받아 맨 뒤에 “\n”를 추가한다.
• 문장을 한 문자씩 검사한다.
  • 문자가 ‘ ‘또는 ‘\n’가 아닌 경우 스택에 추가한다.
  • 문자가 ‘ ‘또는 ‘\n’인 경우 스택에 있는 모든 값을 pop(출력)한 다음, ‘ ‘을 추가한다.

 

💡코드

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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        while(N-- > 0) {
            Stack<Character> stack = new Stack<>();
            String str = br.readLine() + "\\n";
            for(char c : str.toCharArray()) {
                if(c == ' ' || c == '\\n') {
                    while(!stack.isEmpty()) {
                        sb.append(stack.pop());
                    }
                    sb.append(" ");
                } else {
                    stack.push(c);
                }
            }
            sb.append("\\n");
        }

        System.out.println(sb);
        br.close();
    }
}

 

💡시간복잡도

입력받는 문자의 수를 N, 각 문장의 길이를 K라고 할 때, 총 시간복잡도는 O(NK)이다.

 

💡 틀린 이유

BufferedReader.readLine() 가 “\n”를 포함하지 않고 문자열을 반환한다는 것을 생각하지 못했다.

 

💡 틀린 부분 수정

마지막 단어의 처리를 위해 한 문장을 입력받을 때 맨 뒤에 “\n”을 추가해야 했다.

 

💡 느낀점 or 기억할정보

BufferedReader.readLine() 는 개행 문자를 포함하지 않는다는 점을 기억하자!