[백준] 9093 단어 뒤집기 | 구현, 문자열 | 브론즈 Ⅰ | JAVA 💡시간복잡도 아주 간단하게 줄이는 방법

📌 https://www.acmicpc.net/problem/9093

 

✅ Pre-Refactor Code

import java.io.*;

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());
        
        for (int i = 0; i<n; i++){
            String s = br.readLine();
            String[] ss = s.split(" ");
            for (int j = 0; j<ss.length; j++){
                String[] S = ss[j].split("");
                for (int k = S.length-1; k>=0; k--){
                    sb.append(S[k]);
                }
                sb.append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
        
    }
}

이 코드는 일단 StringTokenizer보다 split 메소드가 편해서 split을 통해 문자열을 나누었습니다.

또한, StringBuilder 클래스의 내장 메소드인 reverse 메소드를 몰라 for문을 통해 마지막 인덱스부터 처음 인덱스까지 출력하여 단어 뒤집기를 구현했습니다.

그러다보니 3중 for 문을 통해 문제를 해결해야만 했습니다!

그래서 시간이 880ms가 소요되었는데요..^^

아무리 자바라고 해도 이건 너무하다 싶어서 다른 코드를 참고했습니다.

🙏🏻 acd4548

 

🔄️ Refactored Code 1

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());
        
        for (int i = 0; i<n; i++){
            // String s = br.readLine();
            // String[] ss = s.split(" ");
            StringTokenizer st = new StringTokenizer(br.readLine());
            int count = st.countTokens();
            for (int j = 0; j<count; j++){
                StringBuilder S = new StringBuilder(st.nextToken());
                // for (int k = S.length-1; k>=0; k--){
                //     sb.append(S[k]);
                // }
                sb.append(S.reverse()+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
        
    }
}

이 코드는 StringBuilder 클래스의 reverse 메소드를 활용했는데요!

참고한 코드보다 40ms가 차이나서 아래 코드처럼 고쳐봤습니다.

 

🔄️ Refactored Code 2

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());
        StringTokenizer st;
        
        for (int i = 0; i<n; i++){
            // String s = br.readLine();
            // String[] ss = s.split(" ");
            st = new StringTokenizer(br.readLine());
            int count = st.countTokens();
            for (int j = 0; j<count; j++){
                StringBuilder S = new StringBuilder(st.nextToken());
                // for (int k = S.length-1; k>=0; k--){
                //     sb.append(S[k]);
                // }
                sb.append(S.reverse()).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
        
    }
}

40ms를 줄일 수 있던 방법은 바로 for문 안에서 StringTokenizer를 선언하지 않고 for문 밖에서 선언하는 방법을 사용한 것입니다!

어찌보면 당연한 결과인데요!

첫번째 코드 (Refactored Code 1)에서는 for문 마다 StringTokenizer 객체를 새로 생성하기 때문에 매 for문마다 메모리 할당과 초기화 과정이 발생하여 객체 생성 비용이 누적됩니다.

반면, 두번째 코드 (Refactored Code 2)에서는 for문 밖에서 StringTokenizer 객체를 단 한 번만 생성하고, 이때 생성한 st 변수를 매 for문 마다 재사용하기 때문에, 객체 생성 비용이 훨씬 줄어들게 됩니다.

따라서, 두번째 코드 (Refactored Code 2)처럼 객체를 재사용하게 되면  메모리 관리와 CPU 사용 측면에서 유리해집니다.

 

 

 

🤔 느낀 점

이번 풀이를 통해 객체 재사용의 중요성을 깨달았습니다.

같은 객체를 반복적으로 사용하면 메모리 할당과 해제를 줄일 수 있어 성능이 향상될 수 있다는 것을 알았고, 불필요한 객체 생성을 피하면 가비지 컬렉션 오버헤드를 줄여 CPU 자원을 효율적으로 사용할 수 있다는 것을 알게 되었습니다.

이로 인해 성능을 고려하여 코드를 작성하면 동일한 알고리즘이라도 실행 시간에서 큰 차이를 만들 수 있다는 점을 이해하게 되었습니다.

코드를 더 간결하게 만들기 위해 두 문장에 나눠쓰는 것보다 한 문장으로 표현하는 걸 선호해서 for문 안에서 객체를 생성했더니, 이렇게 큰 시간 손해를 초래할 수 있다는 것을 알게 되었습니다.

앞으로는 코드 작성 시 객체 관리에 주의하여 더 효율적인 프로그램을 만들어야겠다고 생각했습니다!