글 읽기 - 안녕하세요. 시간초과 이유가 궁금합니다.

lunartown 1년 전 0

뒤집는 연산 R과 앞의 요소 하나를 제거하는 D 연산을 구현하는 문제입니다.

뒤집는 연산이 시간이 오래 걸려 rev 변수를 주고 R연산시에 + - 만 바꾸게 하고,

대신 D연산이나 출력시에 rev 상태가 -이면 거꾸로 연산하도록 만들어서

시간초과가 날 부분이 안 보이는데 자꾸 시간초과가 납니다.

도움 주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		LinkedList<Integer> deque;
		String cmd, arr;
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int len, size, rev;
		boolean error;
		
		int T = Integer.parseInt(in.readLine());
		
		for(int i = 0; i < T; i++) {
			deque = new LinkedList<>();
			rev = 1;
			error = false;
			len = 0;
			size = 0;
			
			cmd = in.readLine();
			len = cmd.length();
			
			size = Integer.parseInt(in.readLine());
			arr = in.readLine();
			arr = arr.substring(1, arr.length() - 1);
					
			st = new StringTokenizer(arr, ",");
			
			char[] command = new char[len];
			cmd.getChars(0, len, command, 0);
			
			for(int j = 0; j < size; j++) {
				deque.add(Integer.parseInt(st.nextToken()));
			}
			
			label:for(int j = 0; j < len; j++) {
				switch(command[j]) {
				case 'R' : rev *= -1; break;
				case 'D' : try {
				if(rev == 1) { deque.removeFirst(); }
				else if(rev == -1) { deque.removeLast(); }
				} catch(Exception e) {
					error = true;
					break label;
				}
				}
			}
			
			if(error == true) sb.append("error\n");
			else if (rev == 1){
				sb.append(toString(deque) + "\n");
			}else if(rev == -1) {
				sb.append(revString(deque) + "\n");
			}
		}
		
		System.out.println(sb);
	}
	
	 static String toString(LinkedList<Integer> deque) {
		 String str = "[";
		if (deque.isEmpty()) return str + "]";
		else for(int i = 0; i < deque.size() - 1; i++) {
			str += deque.get(i) + ",";
		}
		str += deque.getLast() + "]";
		return str;
	}

	static String revString(LinkedList<Integer> deque) {
		String str = "[";
		if (deque.isEmpty()) return str + "]";
		else for(int i = deque.size() - 1; i > 0; i--) {
			str += deque.get(i) + ",";
		}
		str += deque.getFirst() + "]";
		return str;
	}
	
}

toString, revString에서 정답 문자열을 만드는 과정이 매우 비효율적입니다. Java의 String 객체는 immutable하기 때문에 72, 82번째 줄과 같은 연산은 모두 기존의 str의 내용을 전부 복사해서 새로운 String 객체를 만든 뒤 그 뒤에 문자열을 덧붙이는 과정을 거칩니다. 그래서 정답 문자열을 하나를 만드는 데에 원소의 수의 제곱에 비례하는 시간이 걸립니다.

lunartown 1년 전 0

안녕하세요, 답변 감사드립니다.

String 만드는 부분을 모두 stringbuilder append로 고쳤는데 여전히 시간초과가 납니다 ㅠㅠ

deque.get(i)부분도 문제인 것 같은데 혹시 좋은 방법이 있을까요?

lunartown 1년 전 0

@djm03178

iterator로 고쳤더니 통과했네요 ㅎ 감사합니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		LinkedList<Integer> deque;
		String cmd, arr;
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int len, size, rev;
		boolean error;
		
		int T = Integer.parseInt(in.readLine());
		
		for(int i = 0; i < T; i++) {
			deque = new LinkedList<>();
			rev = 1;
			error = false;
			len = 0;
			size = 0;
			
			cmd = in.readLine();
			len = cmd.length();
			
			size = Integer.parseInt(in.readLine());
			arr = in.readLine();
			arr = arr.substring(1, arr.length() - 1);
					
			st = new StringTokenizer(arr, ",");
			
			char[] command = new char[len];
			cmd.getChars(0, len, command, 0);
			
			for(int j = 0; j < size; j++) {
				deque.add(Integer.parseInt(st.nextToken()));
			}
			
			label:for(int j = 0; j < len; j++) {
				switch(command[j]) {
				case 'R' : rev *= -1; break;
				case 'D' : try {
				if(rev == 1) { deque.removeFirst(); }
				else if(rev == -1) { deque.removeLast(); }
				} catch(Exception e) {
					error = true;
					break label;
				}
				}
			}
			
			if(error == true) sb.append("error\n");
			else if (rev == 1){
				sb.append("[");
				if (deque.isEmpty()) sb.append("]\n");
				else {
					Iterator<Integer> itr = deque.iterator();
					while(itr.hasNext()) {
						sb.append(itr.next() + ",");
					}
					sb.deleteCharAt(sb.length() - 1);
					sb.append("]\n");
					}
			}else if(rev == -1) {
				sb.append("[");
				if (deque.isEmpty()) sb.append("]\n");
				else {
					ListIterator<Integer> itr = deque.listIterator(deque.size());
					while(itr.hasPrevious())
						sb.append(itr.previous() + ",");
					sb.deleteCharAt(sb.length() - 1);
					sb.append("]\n");
					}
			}
		}
		
		System.out.println(sb);
	}
	
}

djm03178 1년 전 0

아, 그 부분이 느린 것도 맞습니다.

그거는 get 대신 removeFirst와 removeLast로 빼면서 진행하면 됩니다.

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

문제

문제

출처

ICPC

안녕하세요. 시간초과 이유가 궁금합니다.

lunartown 1년 전 0

djm03178 1년 전 1

lunartown 1년 전 0

lunartown 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말