글 읽기 - 왜 시간초과가 뜨는지 모르겠습니다.

maringo 7년 전 0

처음에 ArryaLIst로 해서 시간초과 뜨길래 LinkedList로 바꿔보았습니다.

그런데도 진행되다 시간초과는 뜨는데, 문제점을 못찾겠습니다. 도와주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input =br.readLine();
		int n=Integer.parseInt(input);
		
		String strList[]=new String[n];
		for (int i=0; i<n; i++){
			strList[i]=br.readLine();
		}
				
		for (int line=0; line<n; line++){ //입력받은 라인 갯수
			LinkedList<String> result = new LinkedList<>();
			int index=0;
			for (int i=0; i<strList[line].length(); i++){ //입력받은 라인
				String curStr=strList[line];
				if ( curStr.charAt(i)=='<'){ // '<'를 만났을 때, index 수정
					if (index>0){ 
						index--;
					} else index=0;
				} else if ( curStr.charAt(i)=='>'){ // '<'를 만났을 때, index 수정
					if (index<result.size()){ 
						index++;
					}
				} else if ( curStr.charAt(i)=='-'){ // '-'를 만났을 때, index 수정
					if (index>0){
						result.remove(index-1);
						index--;
					} 
				} else { //문자열 들어갔을 때
					result.add(index, String.valueOf(curStr.charAt(i)));
					index++;
				}
			}
			String temp="";
			for (int i=0; i<result.size(); i++){
				temp+=result.get(i);
			}
			
			System.out.println(temp);
		}
	}
}

zlzmsrhak 7년 전 0

정확한 내용은 검색을 더 해봐야하겠지만, result.add와 result.remove에 인자로 index를 넣은 경우 선형 시간이 걸리게 될 것 같습니다.

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

문제

문제

출처

ICPC

왜 시간초과가 뜨는지 모르겠습니다.

maringo 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말