HS_development_log

백준 1406번 - 에디터 / Java 본문

Algorithm-백준/스택

백준 1406번 - 에디터 / Java

DevHyeonseong 2020. 1. 15. 18:51
반응형

문제

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

 

1406번: 에디터

문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가

www.acmicpc.net

간단한 문자열 조작 문제처럼 보이지만 시간제한이 상당히 짧기 때문에 시간 복잡도를 신경 써서 풀어야 하는 문제.

출력방식도 신경써야될정도로 빡빡하게 제한이 걸려있다.

2개의 스택을 이용하면 O(n) 안에 해결할 수 있다.

 

 

알고리즘

  1. 입력받은 문자열을 커서 기준 왼쪽(이하 left) 스택에 넣는다

  2. L 명령어가 입력 오면 left스택에서 pop 한 것을 right스택에 push 한다. 이때 left스택이 비어있다면 실행하지 않는다

  3. D 명령어가 입력되면 right스택에서 pop 한 것을 left스택에 push 한다. 이때 right 스택이 비어있다면 실행하지 않는다

  4. B 명령어가 입력되면 left스택에서 pop 한다. 이때 left스택이 비어있다면 실행하지 않는다

  5. P 명령어가 입력되면 추가할 문자를 left스택에 push 한다

  6. 출력 시간을 줄이기 위해 StringBuilder 객체의 append를 이용, 문자열을 모두 붙인 후에 한 번에 출력한다

소스코드 및 설명

 

1,2,3,4,5번 알고리즘

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
        for(int i=0;i<str.length();i++) {
            left.push(str.charAt(i));
        }
        for(int i=0;i<m;i++) {
            String com = scan.next();
            if(com.equals("L")) {
                if(!left.isEmpty()) {
                    right.push(left.pop());
                }
            }
            else if(com.equals("D")) {
                if(!right.isEmpty()) {
                    left.push(right.pop());
                }
            }
            else if(com.equals("B")) {
                if(!left.isEmpty()) {
                    left.pop();
                }
            }
            else {
                String word = scan.next();
                left.push(word.charAt(0));
            }
        }
 cs

 

 

6번 알고리즘

 

 

1
2
3
4
5
6
7
8
        StringBuilder sb = new StringBuilder();
        for(char a : left) {
            sb.append(a);
        }
        while(!right.isEmpty()) {
            sb.append(right.pop());
        }
        System.out.println(sb.toString());
 cs

 

 

전체 소스 코드

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
 * BOJ 1406
 * 2020.01.15
 * Hyeonseong
 */
import java.util.*;
public class BOJ1406 {
    public static void main(String[] args) {
        Solution s = new Solution();
    }
}
class Solution{
    String str; // 초기에 입력되는 문자열
    int m; // 입력되는 명령어의 수 
    Solution(){
        Scanner scan = new Scanner(System.in);
        str = scan.nextLine();
        m = scan.nextInt();
        scan.nextLine();
        
        Stack<Character> left = new Stack<Character>();
        Stack<Character> right = new Stack<Character>();
        
        for(int i=0;i<str.length();i++) {
            left.push(str.charAt(i));
        }
        for(int i=0;i<m;i++) {
            String com = scan.next();
            if(com.equals("L")) {
                if(!left.isEmpty()) {
                    right.push(left.pop());
                }
            }
            else if(com.equals("D")) {
                if(!right.isEmpty()) {
                    left.push(right.pop());
                }
            }
            else if(com.equals("B")) {
                if(!left.isEmpty()) {
                    left.pop();
                }
            }
            else {
                String word = scan.next();
                left.push(word.charAt(0));
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char a : left) {
            sb.append(a);
        }
        while(!right.isEmpty()) {
            sb.append(right.pop());
        }
        System.out.println(sb.toString());
    }
}
 
 
 cs
반응형