글 읽기 - 링크드리스트 문제라하여 링크드리스트를 썼는데 시간 초과가 납니다

injoon2018 4년 전 0

질문 게시판에 보니 스택 두개를 이용하는 방법이 있던데 링크드리스트로는 못푸는 문제인가요?

//Baekjoon - 1406

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class BaekJoon1406 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str = br.readLine();
		int M = Integer.parseInt(br.readLine());
		String[] strToken;
		LinkedList<Character> linkedlist = new LinkedList<>();
		int index = str.length();
		for(int i=0; i<str.length(); i++) {
			linkedlist.add(str.charAt(i));
		}
		String cmd;
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M; i++) {
			strToken = br.readLine().split(" ");
			cmd = strToken[0];
			switch(cmd) {
				case "L":{
					if(index>0)
						index--;
						break;
				}
				case "D":{
					if(index<linkedlist.size())
						index++;
					break;
				}
				case "B":{
					if(index>0)
						linkedlist.remove(--index);
					break;
				}
				case "P":{
					linkedlist.add(index, strToken[1].charAt(0));
					index++;
					break;
				}		
			}
		}
		int size= linkedlist.size();
		for(int i=0; i<size;  i++) {
			sb.append(linkedlist.poll());
		}
		bw.append(sb);
		bw.flush();
	}
}

lovinix 4년 전 1

LinkedList.add() , LinkedList.remove() 연산은 O(N)입니다

injoon2018 4년 전 0

@lovinix 더블링크드 리스트를 쓰면 그럼 가능하겠네요??

lovinix 4년 전 0

링크스리스트의 문제가 아니라 단순히 index를 쥐고 remove add하는건 아무 의미가 없다는 이야기입니다.

index를 가지고있는게 아니라 해당하는 위치를 가지고 삽입삭제를 하셔야 O(1)에 remove add를 하실수있습니다.

ListIterator에 대해 공부해보세요

injoon2018 4년 전 0

@lovinix 넵 감사합니다!

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

문제

문제

출처

ICPC

링크드리스트 문제라하여 링크드리스트를 썼는데 시간 초과가 납니다

injoon2018 4년 전 0

lovinix 4년 전 1

injoon2018 4년 전 0

lovinix 4년 전 0

injoon2018 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말