[JAVA] 백준 17413 단어 뒤집기 2

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

17413번: 단어 뒤집기 2

 

1. 서론

 

어쩌다 보니 작년에 풀었던 단어 뒤집기 2 문제를 다시 풀게 되었다. 그때는 C++로 지금은 Java로... 근데 언어만 바뀌었을 뿐인데 신경 써줘야 하는 게 이렇게나 많아질 줄은 몰랐다. 진짜 C++의 속도에 감사하며... 이 문제로 배울 점이 많았다는 것에 또 감사 ㅎ

 

2. 문제 풀이

 

https://coding-log.tistory.com/122

[C++] 백준 17413 단어 뒤집기 2

1년 전에 풀었던 풀이과정과 유사해서 놀랐다. 보고 푼 거 아닌데... 똑같은 사람이 푼 게 맞긴 하구나^^ (완전 동일하지는 않음)

 

말 그대로 단어를 뒤집는 문제이다. 단어는 공백문자로 구분하며 < > 태그 안의 단어는 뒤집지 않는다. 그러나 태그 사이에 있는 단어는 뒤집어야 한다.

 

그래서 입력받은 문자열을 <> 따로, 뒤접어야 하는 단어를 따로 저장해서 값을 처리한 후 다시 합쳤다.

공백 문자를 단위로 단어로 구분되고, 태그 안에 있는 것도 단어로 구분되기 때문에 그 조건 들일 때만 문자열을 뒤집는 방법으로 문제를 풀었다. 당연히 테스트 케이스가 잘 돌아가서 코드를 냈는데 생각지도 못하게 시간 초과가 나왔다. java8 버전으로 돌리니까 시간 초과가 나서 찾아보니 java11로 하면 돌아간다고 해서 java11 버전으로 돌리니까 맞았다고 떴다. 너무 황당해서 왜 이러는지 8 버전에서는 어떻게 해야 시간 초과가 안 날까 연구하면서 찾아본 결과 내 코드의 문제는 반복문을 써서도 아니고 바로 'String'을 써서였다. String 자체가 무겁고? 이 문제 같은 경우에는 +로 계속 단어를 처리하고 붙여줘야 해서.. (+ 자체가 실행시간이 오래 걸림, 그래서 출력할 때 + 많이 쓰니까 출력할 때만 StringBuilder를 써서 무슨 기능을 하는지 잘 몰랐는 String처럼 쓸 수 있다는 사실을 이 문제를 풀면서 깨우침) 그래서 String을 안 쓰면 도대체 이걸 어떻게 처리하나 생각하다가 String 대신에 StringBuilder를 썼더니 눈에 띄게 시간이 줄어들었고 java8에서도 코드가 돌았다.

 

 

진짜 C++은 8ms인데... java 시간은 언제봐도 적응이 안 된다 ㅎ 11로 돌리니까 돌고 8로 돌리니까 안돼서 String을 전부 StringBuilder로 바꿔준 결과 시간과 메모리가 말도 안 되게 줄어들었다. 이거 완전 꿀팁인 듯... 

 

그래서 이 문제 이후로 StringTokenizer, StringBuilder, BufferedReader 전부 애용중이다.(시간초과 트라우마 생겨서 ㅎ)

C++로 풀 때는 고려 안했던 부분까지 죄다 신경 써줘야 해서 진짜 별로다... Java는 확실히 개발하기에는 좋지만 알고리즘 풀기에는 적절한 언어는 아닌 듯... ㅎ

 

3. 코드 설명

 

import java.io.*;

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

        String s = br.readLine();
        for (int i = 0; i < s.length(); i++) {
        	if (s.charAt(i) == '<') {
        		sb.append(s.charAt(i++));
        		while(s.charAt(i) != '>')
        			sb.append(s.charAt(i++));
        		sb.append(s.charAt(i));
        	}
        	else
        		if (s.charAt(i) != ' ')
        			tmp.append(s.charAt(i));
        
        	if ((i + 1 < s.length() && s.charAt(i + 1) == '<' )|| i == s.length() - 1 || (i + 1 < s.length() && s.charAt(i + 1) == ' ' )) {
        		if (tmp.length() > 0)  {
        			sb.append(tmp.reverse());
        			tmp.setLength(0);
        		}
        		if (i + 1 < s.length() && s.charAt(i + 1) == ' ')
        			sb.append(" ");
        	}
       }
        bw.write(sb.toString());
        bw.flush(); bw.close(); br.close();
    }
}

 

 

실행속도를 조금이라도 줄여보고자 온갖 것이 다 총출동했다. BufferedReader, Writer로 읽고 쓰고 String 대신 StringBuilder를 String처럼 사용했다. 이런 게 있는지도 몰라서 이렇게 활용할 수 있다는 사실도 이 문제를 통해 알게 되었다...

sb에다가 출력할 문장을 저장할 것이기 때문에 태그 안에 있는 값들은 그냥 다 sb에 넣고 뒤집어야 하는 단어들은 tmp에 넣고 뒤집은뒤 sb에 넣어줬다. 그리고 원래 단어 사이에는 공백 문자가 있기 때문에 공백 문자도 넣어주었다.

단어를 찾는 조건은 단어 뒤에 공백문자가 들어왔거나 태그 사이에 있을 때는 '<'의 앞에서 끊기기 때문에 이걸 조건으로 삼아서 단어를 나누고 그 값을 뒤집어서 sb에 넣어줬다. 

 

그리고 새로 알게 된 점!! StringBuilder 초기화(재활용) 하려면 setLength(0) 즉 길이를 0으로 만들어 버리면 됨!!

그리고 .reverse() 하면 그냥 뒤집어짐.

그리고 bw를 통해 출력해줬다.