글 읽기 - 자바 11 시간초과 이유가 궁금합니다.

iwtl0303 1년 전 0

자꾸 시간초과 오류가 뜨네요. 이중 for문도 아닌데 이유가 뭘까요...

입출력 시간 줄이려고 bufferReader랑 bufferWriter도 씁니다.

알려주시면 감사하겠습니다.

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

public class Main{
    static int num;
    static int idx=0;
    static int maxidx=0;
    static String command;
    static String cword;
    static String word;
    static String[] words;
    static LinkedList<String> list = new LinkedList<String>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        word = br.readLine();
        words = word.split("");
        for(int i = 0; i < word.length(); i++){
            list.add(words[i]);
            maxidx++;
            idx++;
        }
        num = Integer.parseInt(br.readLine());

        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            command = st.nextToken();
            if (command.equals("P")){
                cword = st.nextToken();
                list.add(idx,cword);
                maxidx++;
                idx++;
            }
            else if(command.equals("L")&& idx>0){
                idx--;
            }
            else if(command.equals("D")&& idx<maxidx){
                idx++;
            }
            else if(command.equals("B")&& idx>0){
                list.remove(idx-1);
                maxidx--;
                idx--;
            }

        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(String i : list){
            bw.write(String.valueOf(i));
        }
        bw.close();
}
}

sdpr 1년 전 2

list.add(k), list.remove(k)는 O(k)입니다. 왜냐면 연결리스트는 k번째 인덱스를 저장하고 있지 않거든요. 매번 처음부터 출발해서 k번째를 찾아낸 뒤 이를 삭제합니다.

현재 노드를 포인터로 갖고있는 요소를 추가해보면 어떨까요?

iwtl0303 1년 전 0

답변 감사합니다. 그렇게 구현해보겠습니다.

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

문제

문제

출처

ICPC

자바 11 시간초과 이유가 궁금합니다.

iwtl0303 1년 전 0

sdpr 1년 전 2

iwtl0303 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말