글 읽기 - 에디터(1406) 시간초과가 해결되지 않습니다.

kisp1049 7년 전 0

안녕하세요. 에디터 문제 풀고 있는 중인데.

테스트 케이스에 대해서는 다 잘 돌아가는데 시간초과가 해결되지 않습니다.

저는 스택을 이용해서 문자를 넣고 빼고해서 에디터를 구현하려고 했습니다.

제가 생각한 경우에는 처음 사용자가 입력하는 문자열을 배열로 저장하는 반복 1번, 명령어 개수만큼의 while반복 1번, 출력하기 위해 왼쪽 스택에 있는 문자 배열을 오른쪽 스택으로 옮기는 pop&push하는 for문 1번, 오른쪽 스택에 모든 배열을 출력하기 위한 for문 1번으로 4번의 반복문은 최소한 필요하다고 생각이 듭니다. 지금 반복문이 많아서 시간초과가 뜨는 것인지 아니면 다른 분들은 버퍼리더 이용해서 입력받은 분들 계시던데 그 차이인지 어떤 코드가 시간복잡도가 크게 잡는 부분인지 알고 싶습니다. 알고 고수 여러분! 한 수 부탁드리겠습니닷.

import java.util.Scanner;
import java.util.Stack;

public class P1406 {

	public static void printLine(Stack<Character> stL, Stack<Character> stR) {
		while(!stL.empty()){
			stR.push(stL.pop());
		}
		while(!stR.empty()){
			char chR = stR.peek();
			System.out.print(chR);
			stR.pop();
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Character> stL = new Stack<>();
		Stack<Character> stR = new Stack<>();
		char topEl;
		
		char[] inputLine = sc.nextLine().toCharArray();
		for(char ch : inputLine)	//init
			stL.push(ch);

		int opNum = sc.nextInt();
		sc.nextLine();
		while(true){
			opNum--;
			String operation = sc.nextLine();	//operation

			if(operation.contains("L")){	//커서 왼쪽 한칸 이동
				if(!stL.isEmpty()){
					stR.push(stL.pop());
				}
			} else if(operation.contains("D")){	//커서 오른쪽 한칸 이동
				if(!stR.isEmpty()){	//커서 맨 오른쪽 끝 아닌 경우
					stL.push(stR.pop());
				}
			} else if(operation.contains("B")){	//커서 왼쪽 문자 삭제
				if(!stL.isEmpty())
					stL.pop();
			} else if(operation.contains("P")){	//$오른쪽 추가, 커서 $ 오른쪽
				char newChar = operation.charAt(2);
				stL.push(newChar);
			}	

			if(opNum == 0) break;
		}
		printLine(stL,stR);
		sc.close();
	}

}

sgchoi5 7년 전 1

저는 동일한 방식으로 C++11 로 한 경우라 로직은 문제가 없는 것 같고, 입출력 시간의 문제인 것 같습니다.

Java 로 stack 이용해서 푸신 분 코드 보니 입력 처리를 Scanner 대신에 BufferedReader 쓰셨네요. 참고하시길....

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

kisp1049 7년 전 0

감사합니다.

버퍼리더 쓰니까 해결이 되는군요?!!

혹시 스캐너를 쓰는 경우와 버퍼리더를 쓰는 경우에 시간 차이가 이렇게 나는건지 알고 계신가요?

sgchoi5 7년 전 1

입출력 성능 비교: algospot https://algospot.com/forum/rea... 에 대한 글이 있네요.. 참고하시고..

구글에 "Scanner BufferedReader 성능" 으로 한 번 검색해 보시길...

kisp1049 7년 전 0

감사합니다~!

덕분에 많이 배우고 갑니다!!ㅎㅎ

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

문제

문제

출처

ICPC

에디터(1406) 시간초과가 해결되지 않습니다.

kisp1049 7년 전 0

sgchoi5 7년 전 1

kisp1049 7년 전 0

sgchoi5 7년 전 1

kisp1049 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말