[백준 | 9093] 단어 뒤집기 - Java

문제

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

입력

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

출력

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

예제 입력

입력	출력
2 I am happy today We want to win the first prize	I ma yppah yadot eW tnaw ot niw eht tsrif ezirp

내 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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));

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");

            for (int j = 0; j < str.length; j++) {
                str[j] = new StringBuilder(str[j]).reverse().toString();
            }

            bw.write(String.join(" ", str));
            bw.newLine();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

풀이과정

문자열을 공백 단위로 분리한 후, StringBuilder의 reverse() 메서드를 사용하여 각 문자열을 뒤집어 다시 저장하였습니다. 뒤집은 문자열을 출력할 때는 String.join() 메서드를 사용하여 배열의 요소들을 공백으로 연결하였습니다.

 

시간 복잡도 분석

이 코드의 시간 복잡도는 입력 크기 N과 각 단어의 최대 길이 L에 비례합니다.

• N: 테스트 케이스의 개수
• L: 각 단어의 최대 길이 (최대 20)

각 테스트 케이스에서 입력된 문장을 공백으로 분리하고, 각 단어를 뒤집는 작업은 모두 O(L)의 시간이 걸리며, 전체 문장을 처리하는 데는 O(N * L)의 시간이 소요됩니다.따라서 이 코드의 전체 시간 복잡도는 $O(N * L)$입니다. 여기서 N은 입력된 테스트 케이스의 개수, L은 각 단어의 길이입니다.