BOJ(백준 온라인 저지) 1406번 with 자바[JAVA]

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

1406번: 에디터

---

(이미지는 화질이 너무 깨져서 첨부 못함)

 

문자열을 입력받고 명령에 따라 문자열을 편집하는 문제이다.

 

우선 나는 String의 substring()을 이용하여 문제를 풀었다.

 

코드를 보자.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		
		// cursor의 위치를 index로 나타내었다.
		int cursor = str.length();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			char op = st.nextToken().charAt(0);
			
			switch(op) {
			
			case 'L':
				// cursor의 위치가 문장의 맨 앞이 아닐경우 커서의 index를 하나 줄임
				if(cursor > 0)
					cursor--;
				break;
				
			case 'D':
				// cursor의 위치가 문장의 맨 뒤가 아닐경우 커서의 index를 하나 늘림
				if(cursor <  str.length())
					cursor++;
				break;
				
			case 'B':
				// cursor의 위치가 문장의 맨 앞이 아닐경우
				if(cursor > 0) {
					// 0부터 cursor전까지의 문자열 + cursor부터 끝까지의 문자열
					str = str.substring(0, cursor - 1) + str.substring(cursor);
					// 문자가 하나 줄었으니 cursor도 하나 줄여준다.
					cursor--;
				}
				break;
				
			case 'P':
				// 입력받을 문자
				char ch = st.nextToken().charAt(0);
				// 0부터 cursor전까지의 문자열 + 추가하고픈 문자열 + cursor부터 끝까지의 문자열
				str = str.substring(0, cursor) + ch + str.substring(cursor);
				// 문자가 하나 늘었으니 cursor도 하나 늘려준다.
				cursor++;
				break;
				
			}
		}
		
		System.out.println(str);
 	}
}

 

결과는 시간초과!

 

그 이유는 시간복잡도 때문이라고 생각한다.

 

cursor을 ++하거나 --하는것은 O(1) 이기 때문에 상관은 없지만 문제는 B나 P연산이다.

M <= 500,000, N <= 100,000 이기 때문에 시간초과는 당연했었다.

 

음... 너무 어려워서 구글링을 했다.

스택을 이용했더라...

 

문자열을 커서를 기준으로 왼쪽 스택, 오른쪽 스택을 나눈다.

그리고 명령들을 수행한다.

이렇게 하면 시간 초과는 해결된다.

 

코드를 보자.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String str = br.readLine();
		
		Stack<Character> left = new Stack<>();
		Stack<Character> right = new Stack<>();
		
		for(int i=0; i<str.length(); i++) {
			
			left.push(str.charAt(i));
			
		}
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			char op = st.nextToken().charAt(0);
			
			switch(op) {
			
			case 'L':
				if(!left.isEmpty()) {
					
					char ch = left.pop();
					right.push(ch);
					
				}
				break;
				
			case 'D':
				if(!right.isEmpty()) {
					
					char ch = right.pop();
					left.push(ch);
					
				}
				break;
				
			case 'B':
				if(!left.isEmpty()) {
					
					left.pop();
					
				}
				break;
				
			case 'P':
				char ch = st.nextToken().charAt(0);
				
				left.push(ch);
				
				break;
			
			}
		}

		
		Iterator<Character> itLeft = left.iterator();
		while(itLeft.hasNext()) 
			right.push(itLeft.next());
		
		Iterator<Character> itRight= right.iterator();
		while(itRight.hasNext())
			sb.append(itRight.next());
		
		System.out.print(sb); 
 	}
}

 

 

 

 

---

• 느낀 점

단어 뒤집기, 괄호 문제, 에디터 문제에서 스택을 사용했는데

LIFO를 이용하는 경우나

문자열같은 배열을 반으로 쪼개서(고구마 같이 ㅎ) 이용할 때

Stack을 사용하면 될거같다.

 

 

 

+ 시간복잡도를 생각하면서 문제를 풀면 오답 없이 깔끔하게 풀 수 있을 것 같다