글 읽기 - 에디터 시간초과 질문드립니다.

exponential_e 5년 전 0

예제는 일단 모두 통과하는데요. 6~7%에서 계속 시간초과가 납니다.

리스트의 add remove get이 문제인듯 싶기도하고..

처음에 문제 보자마자 리스트로 구현하면 될 것 같았는데, 질문검색해보니 스택 이용하시는 분들이 많더라구요.

아직 풀진못해서 그분들의 코드를 자세히 보진 않았는데.. 혹시 두 stl 성능 차이가 많이 나나요??

아니면 제가 이 문제 자체를 잘못 접근하고있는 걸까요?? 답변 부탁드려요~

코드도 참고로 한번 올려봅니다!

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

public class Boj1406 {
	private static final String PUSH = "D";
	private static final String PULL = "L";
	private static final String REMOVE = "B";
	private static final String ADD = "P";
	private static final char INIT = '0';
	
	private static LinkedList<Character> words = new LinkedList<>();
	private static int cursor = 0;
	
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws Exception{		
		words.add(INIT);                // 초기에 임의의 값 하나를 미리 추가
		char[] tmp = br.readLine().toCharArray();
		for(int i = 0; i < tmp.length; i++) {    // 입력으로 들어온 캐릭터 값을 리스트로 재할당
			words.add(tmp[i]);
		}
		
		cursor = words.size() - 1;                // 커서
        int N = Integer.parseInt(br.readLine());  // 명령어 갯수
		
		while(N-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String cmd = st.nextToken();
			char w = ' ';
			
			try {        // 명령이 2개가 들어올 경우 (e.g. "P $")
				w = st.nextToken().charAt(0);
			}
			catch(NoSuchElementException nsee) {
				
			}
			
			int limit = words.size() - 1;
			
			switch (cmd) {        // PUSH(D), PULL(L), REMOVE(B), ADD(P)
			case PUSH:                    // 커서 우측으로
				if(cursor == limit) break;
				cursor += 1;
				break;
				
			case PULL:                // 커서 좌측으로
				if(cursor == 0) break;
				cursor -= 1;
				break;
			
			case REMOVE:              // 커서 왼쪽의 단어 제거
				if(cursor == 0) break;
				words.remove(cursor);
				cursor -= 1;
				break;
					
			case ADD:                // 커서 왼쪽에 단어 추가
				words.add(cursor + 1, w);
				cursor += 1;
				break;
			}	
		}
		// 출력
		int loop = words.size();
		for(int i = 1; i < loop; i++) {
			bw.write(words.get(i));
		}
		
		bw.flush();
	}
}

jh05013 5년 전 1

반드시 전체 코드를 올려 주세요. 이 상태로는 words가 뭔지 알 수 없고, 디버깅도 불가능하며, 애초에 저기가 문제라는 보장도 없습니다.

exponential_e 5년 전 0

아 그렇군요! 알겠습니다~ 수정하도록 할게요!!

jh05013 5년 전 1

지금 words는 int형의 cursor가 가리키는 것이 무엇인지 기억하지 않기 때문에, add(cursor, x)나 remove(cursor)를 할 때마다 한 쪽 끝에서 cursor까지 일일히 이동해야 합니다. 그래서 시간초과가 납니다.

int 대신 LinkedList.Entry를 저장하면 O(1)만에 추가, 삭제할 수 있습니다.

exponential_e 5년 전 0

와 그런문제였군요... 정말 감사합니다!! 코드 수정해보겠습니다~

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

문제

문제

출처

ICPC

에디터 시간초과 질문드립니다.

exponential_e 5년 전 0

jh05013 5년 전 1

exponential_e 5년 전 0

jh05013 5년 전 1

exponential_e 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말