글 읽기 - [java] 대체 시간초과 나는 이유가 멀까요??

junghun9102 6년 전 1

배열을 만드려면 split은 당연히 해야하는 것이고

함수 p 길이만큼 상수시간씩 수행하고

남겨진 배열 back-front만큼 문자열 붙이는

시간이 많이 걸릴부분이 없어보이는데

당최 왜 시간초과가 날까요? ㅂㄷㅂㄷ

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

public class Main {
	public static void main(String[] args) throws IOException{
		//Init
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder resultStr = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0;i<T;i++) {
			String instructions = br.readLine(); //함수 p
			int n = Integer.parseInt(br.readLine()); //배열에 들어있는 수의 개수
			String inputStr = br.readLine(); //배열
			
			String arr[] = null;
			if(n!=0) {
				arr = inputStr.substring(1, inputStr.length()-1).split(",");
			}
			
			int front = 0;
			int back = n;
			
			//R(뒤집기) 함수가 실행될 때 반대방향에서 버리거나 반대방향부터 출력
			boolean isFront = true; 
			boolean noError = true;
			
			for(int j=0;j<instructions.length()&&noError;j++) {
				String instruction = instructions.substring(j, j+1);
				if(instruction.equals("R")) {
					isFront = !isFront;
				}else if(instruction.equals("D")) {
					String popedNum = null;
					if(isFront) {
						if(front<back) {
							popedNum = arr[front++];
						}
					}else {
						if(front<back) {
							popedNum = arr[--back];
						}
					}
					if(popedNum==null) {
						noError = false;
					}
				}
			}
			
			if(noError) {
				String result = "[";
				if(isFront) {
					for(int j=front;j<back;j++) {
						result+=arr[j];
						if(j!=back-1) {
							result+=",";
						}
					}
				}else {
					for(int j=back-1;j>=front;j--) {
						result+=arr[j];
						if(j!=front) {
							result+=",";
						}
					}
				}
				result+="]";
				resultStr.append(result).append('\n');
			}else {
				resultStr.append("error").append('\n');
			}
		}
		
		//Output
		System.out.println(resultStr.toString());
		br.close();
	}
}

result 문자열을 만들어가는 과정이 문제이지 않을까 싶습니다. 자바에서 String 객체는 immutable 하기 때문에, += 을 할 때마다 두 문자열의 내용을 완전히 다른 곳에 새로 복사해야 됩니다. 즉, +=을 n번 수행하는 시간 복잡도는 n^2이나 됩니다. 배열에 들어있는 수가 10만개까지 되니, 한 번의 테스트 케이스로도 충분히 시간 초과가 날 수 있습니다. result도 StringBuilder로 하면 되지 않을까 싶습니다.

junghun9102 6년 전 0

감사합니다 ㅜ

덕분에 해결했습니다^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[java] 대체 시간초과 나는 이유가 멀까요??

junghun9102 6년 전 1

djm03178 6년 전 1

junghun9102 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말