[BOJ_1406/JAVA] 에디터

[BOJ_1406/JAVA] 에디터

https://www.acmicpc.net/problem/1406

문제

풀이

나는 정답률이 26%길래 조금 겁먹었지만 그래도 풀어보자란 생각에 풀었다.

그런데 머야?! 벌써 다 풀었짢아?! 완전 괜찮은데? 실력이 향상했나 우후후 ^^

햇떤 내가 멍청이엇다.

'시간초과'..

그렇다. 이 문제는 다들 시간초과때문에 정답률이 낮았던 것이엇다.

아래는 내가 풀었던 방식.

커서를 직접 인덱스로 이동하면서 insert와 delete로 풀었다. 하지만 이러면 당연히 시간초과가 난다. 왜?

insert와 delete할때마다 배열의 인덱스를 전부 돌아야하기때문에 문자열+반복문의 횟수까지 하면 시간초과가 당연히 날 수 밖에..

따라서 스택이 push하고 pop을 할때 굉장히 빠르다는 것.. 적어도 반복문의 횟수만큼만 돌면 되기 때문이다.

따라서 스택을 두개를 준비한다.

L : 커서를 한칸 왼쪽으로 이동 -> 왼쪽 스택을 pop해 오른쪽 스택에 push

D : 커서를 한칸 오른쪽으로 이동 -> 오른쪽 스택을 pop해 왼쪽 스택에 push

B : 커서 왼쪽에 있는 문자 삭제 -> 왼쪽 스택 pop

P : 다음에 주어지는 문자를 커서 왼쪽에 삽입 -> 왼쪽 스택 push

이렇게 풀면 굉장히 빠르대...!

코드

틀린 코드 (내가 한 코드)

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class BOJ1406 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; String input = br.readLine(); int num = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); sb.append(input); int cursor = input.length(); for(int i=0;i

정답 코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class BOJ1406 { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st; String input = br.readLine(); int num = Integer.parseInt(br.readLine()); Stack left = new Stack<>(); Stack right = new Stack<>(); for(int i=0;i

이거를 문제보자마자 스택을 써서 해결할 생각을 하다니... 다들 천재인가보다.

from http://silvergal.tistory.com/79 by ccl(A) rewrite - 2021-12-15 17:26:54