[BOJ 길라잡이/Java] 5일차 #1406 에디터

알고리즘 분류

- 자료 구조

- 스택

- 연결 리스트

 

알고리즘에 스택과 연결 리스트가 있는데

나는 이 방법을 사용하지 않고 cursor의 위치를 잡아서 왔다갔다 하고

StringBuffer의 메서드들을 사용했다.

이 참에 StringBuilder와 StringBuffer도 정리해봐야겠다.

 

StringBuffer 사용

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String word = br.readLine();
        StringBuffer buf = new StringBuffer(word);
        int cursor = word.length();

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String com = st.nextToken();
            if (com.equals("L")) {
                if (cursor > 0) {
                    cursor -= 1;
                }
            }
            else if (com.equals("D")) {
                if (cursor < buf.length()) {
                    cursor += 1;
                }
            }
            else if (com.equals("B")) {
                if (cursor > 0) {
                    buf.delete(cursor - 1, cursor);
                    // buf.replace(cursor - 1, cursor, "");
                    cursor -= 1;
                }
            }
            else if (com.equals("P")) {
                String addWord = st.nextToken();
                buf.insert(cursor, addWord);
                cursor += 1;
            }
        }

        System.out.println(buf.toString());
    }
}

 

StringBuffer 내장함수(메소드)

- 문자열 추가

StringBuffer(StringBuilder).append()

 

- 문자열 삽입

StringBuffer(StringBuilder).insert(int offset, String str)

원하는 인덱스에 문자열을 삽입

 

- 문자열 삭제

StringBuffer(StringBuilder).delete(int start, int end)

start(포함) ~ end(미포함)까지 문자열을 삭제

 

- 문자열 변경

StringBuffer(StringBuilder).replace(int start, int end, String str)

start(포함) ~ end(미포함)까지의 구간을 str문자열로 변경

 

- String 객체로 변환

StringBuffer(StringBuilder).toString()

 

StringBuffer와 StringBuilder의 차이

흠 그럼 이 둘은 어떤 차이가 있을지 찾아보니

멀티쓰레드 환경에서 문자열 조작이 필요한 경우에는 StringBuffer를 쓰고

싱글쓰레드 환경에서 빠른 성능이 필요한 경우에는 StringBuilder를 쓴다는데..

코테에서는 뭘 써도 상관 없을 듯하다.

제공하는 메서드도 동일하다!

 

Stack 사용

스택은 모든 연산이 O(1)의 시간 복잡도를 가지기 때문에 시간 초과에 걸리지 않는다.

커서의 왼쪽, 오른쪽 구분을 위해 두 개의 스택을 사용한다.

 

맨 처음 커서는 입력 문자열의 맨 뒤에 위치하므로

처음 문자열을 모두 왼쪽 스택에 넣어준다.

이후 차례로 명령어를 처리하면서 커서가 왼쪽으로 이동하면 왼쪽 스택의 가장 상단 요소를 오른쪽 스택에 pop() 시켜준다.

그리고 커서가 오른쪽으로 이동하면 오른쪽 스택의 가장 상단 요소를 왼쪽 스택에 pop() 시켜주며

마치 커서가 이동하는 것처럼 구현한다.

 

마지막 모든 명령어를 처리한 후에는 스택이 LIFO 구조이기 때문에

왼쪽 스택의 모든 요소들을 오른쪽 스택에 옮긴 후 오른쪽 스택을 모두 pop() 시키며 결과를 출력한다.

 

생각해보지 못한 신기하고 재밌는 방법이다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String word = br.readLine();
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(br.readLine());
        Stack<String> left = new Stack<>();
        Stack<String> right = new Stack<>();

        String[] arr = word.split("");
        for (String a : arr) {
            left.push(a);
        }
        
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String com = st.nextToken();
            
            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 if (com.equals("P")) {
                String addWord = st.nextToken();
                left.push(addWord);
            }
        }

        while(!left.isEmpty()) {
            right.push(left.pop());
        }
        while(!right.isEmpty()) {
            sb.append(right.pop());
        }

        System.out.println(sb.toString());
    }
}

참고 출처: https://minhamina.tistory.com/17

[백준 - Java] 1406번 : 에디터

 

뇌를 말랑말랑하게.. 만들자