글 읽기 - JAVA 시간 초과좀 도와주세요 ㅠㅠ

ast3138 11달 전 0

시간 죽일수 있는건 다죽인거 같은데 50%쯤에서 자꾸 시간초과가 나네요

StringBuilder insert,delete가 시간을 많이 잡아먹나요?

조언 부탁드립니다.

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

public class Main {
		
	public static void main(String[] args) throws Exception {
		BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter output=new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder str=new StringBuilder();
		str.append(input.readLine());
		int n=Integer.parseInt(input.readLine()); //몇번 for문 할지
		int cursor=str.length();
		char ch = 0; //대문자 구분
		for(int i=1;i<=n;i++)
		{
			StringTokenizer st=new StringTokenizer(input.readLine());
			ch=st.nextToken().charAt(0); //대분자 입력받기
				if(ch=='P') //커서 왼쪽에 추가
				{
					char c=st.nextToken().charAt(0);
					str.insert(cursor, c);
					cursor++;
				}
				else if(ch=='L') //커서 왼쪽으로 이동
				{
					if(cursor!=0)
						cursor--;
				}
				else if(ch=='D') //커서 오른쪽으로 이동
				{
					if(cursor!=str.length())
						cursor++;
				}
				else  //ch=='B'
				{
					if(cursor==str.length())
						str.deleteCharAt(--cursor);
					else if(cursor!=0)
					str.deleteCharAt(--cursor);
				}
			}
			
		     output.write(str.toString());
		     output.close();
		
		// TODO Auto-generated method stub

	}

}

djm03178 11달 전 3

내부가 배열 형태로 되어있는 자료구조는 어떻게 해도 중간에 삽입 / 삭제가 O(N)이 될 수밖에 없습니다. 항상 연속성을 유지해야 하기 때문에 빈 공간을 만들거나 메우기 위해 그 뒤의 원소들을 전부 밀거나 당겨야 하기 때문입니다.

ast3138 11달 전 0

역시...그 문제였네요 감사합니다 갓!!!

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

문제

문제

출처

ICPC

JAVA 시간 초과좀 도와주세요 ㅠㅠ

ast3138 11달 전 0

djm03178 11달 전 3

ast3138 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말