[백준 17413, Java] 단어 뒤집기2

문제 

www.acmicpc.net/problem/17413

17413번: 단어 뒤집기 2

check

1. String과 StringBuilder

- 처음에는 String을 사용해서 구현을 했는데 시간초과가 났다. 시간복잡도를 계산했을 때, 모든 문자열이 스택에 push 되었다가 pop되니까 O(2N)이라고 생각했다. 그래서 시간초과가 나는게 의아했다.

- String을 사용했을때에 문제는 String을 이용한 연산때문에 시간초과가 난다는 거다. String에대한 연산이 많을 때는 StringBuilder나 StringBuffer를 사용해야한다. 

 

2. Java9 Java11

- String과 StringBuffere 의 실행시간이 궁금해서 System.currentTimeMills()를 찍어봤는데 String이 더 빠르게 나왔다. 

그래서 Java8로 채점되어있던걸 Java11로 바꾸니 시간초과가 안난다. 

 

cjh5414.github.io/why-StringBuffer-and-StringBuilder-are-better-than-String/

StringBuffer, StringBuilder 가 String 보다 성능이 좋은 이유와 원리

12bme.tistory.com/42

[자바] String, StringBuilder, StringBuffer의 차이

 

ifuwanna.tistory.com/221

[Java] String, StringBuffer, StringBuilder 차이 및 장단점

코드

1. String 사용(시간 초과)

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();

        String line = br.readLine()+" ";
        int index = 0;
        String inverseWord ="";
        while(index<line.length()){
            char alphabet = line.charAt(index);
            if(line.charAt(index)=='<'){
                if(stack.isEmpty()){
                    while(line.charAt(index)!='>'){
                        inverseWord+=Character.toString(line.charAt(index++));
                    }
                }
                else{
                    while(!stack.isEmpty()) {
                        inverseWord += Character.toString(stack.pop());
                    }
                }
            }
            else if(line.charAt(index)=='>'){
                inverseWord+=Character.toString(line.charAt(index++));
            }
            else if(line.charAt(index)==' '){
                if(!stack.isEmpty()){
                    while(!stack.isEmpty()){
                        inverseWord+=Character.toString(stack.pop());
                    }
                    inverseWord+=" ";
                }
                index++;
            }
            else{
                stack.push(line.charAt(index++));
            }
        }

        System.out.println(inverseWord);

    }
}

 

 

 

2. StringBuilder

 

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();

        String line = br.readLine()+" ";
        int index = 0;
        StringBuilder inverseWord =new StringBuilder();
        while(index<line.length()){
            char alphabet = line.charAt(index);
            if(line.charAt(index)=='<'){
                if(stack.isEmpty()){
                    while(line.charAt(index)!='>'){
                        inverseWord.append(Character.toString(line.charAt(index++)));
                    }
                }
                else{
                    while(!stack.isEmpty()) {
                        inverseWord.append(Character.toString(stack.pop()));
                    }
                }
            }
            else if(line.charAt(index)=='>'){
                inverseWord.append(Character.toString(line.charAt(index++)));
            }
            else if(line.charAt(index)==' '){
                if(!stack.isEmpty()){
                    while(!stack.isEmpty()){
                        inverseWord.append(Character.toString(stack.pop()));
                    }
                    inverseWord.append(" ");
                }
                index++;
            }
            else{
                stack.push(line.charAt(index++));
            }
        }

        System.out.println(inverseWord);

    }
}