[백준 JAVA] 1406 에디터

1406 에디터

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

 

문제설명

stack을 사용해서 데이터 순서에 따라 삽입 및 삭제

접근방식

O(n + m) 선형 시간복잡도

1. • L 명령어 (왼쪽으로 커서 이동): leftSt에서 pop하고 rightSt로 push → O(1)
   • D 명령어 (오른쪽으로 커서 이동): rightSt에서 pop하고 leftSt로 push → O(1)
   • B 명령어 (커서 왼쪽 문자 삭제): leftSt에서 pop → O(1)
   • P 명령어 (문자 추가): leftSt에 push → O(1)
2. 문자열 출력: leftSt에 남아있는 문자들을 모두 rightSt로 옮기고, rightSt를 순회하며 출력 → O(N)

따라서 전체 시간 복잡도는 초기 문자열의 길이 N과 명령어 개수 M에 따라 결정된다.

명령어는 O(1) 시간복잡도로 처리되며, 문자열 출력 처리가 O(N) 시간이 걸린다.

총 시간 복잡도는 O(N + M)이다.

문제 조건 분석 과정

 

스택 활용: 왼쪽 스택과 오른쪽 스택을 사용하여 커서의 위치를 기준으로 문자열을 관리한다.

결과 출력: 마지막에 rightSt를 역순으로 꺼내어 StringBuilder에 추가하고, 최종적으로 결과 문자열을 출력한

자료구조

Stack (Stack<Character> leftSt, rightSt)

• leftSt: 왼쪽 스택으로, 초기 문자열을 문자 단위로 역순으로 저장한다.
• 커서를 기준으로 왼쪽에 있는 문자들을 관리한다.
•  
• rightSt: 오른쪽 스택으로, 왼쪽 스택에서 pop된 문자들을 순서대로 저장한다.
• 커서를 기준으로 오른쪽에 있는 문자들을 관리한다.

틀린이유

문제를 이해 못해서 백준 문제를 다시 읽어보는데에만 시간이 오래 소요되었다.

문제를 보는 연습 필요

올바른 접근 방식 및 해결 방식

각 명령어 처리 시 스택이 비어 있는지 확인하기

처음엔 linkedlist를 사용했다가 시간 초과가 나버렸다.

stack은 연산이 o(1)의 상수 시간을 가지기 때문에  시간 초과를 방지할 수 있음

전체코드

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

public class Main_1406에디터 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine(); //초기 문자열
        int M = Integer.parseInt(br.readLine()); //명령어 개수

        Stack<Character> leftSt = new Stack<>(); //왼쪽 스택 (커서 기준 왼쪽 문자열)
        Stack<Character> rightSt = new Stack<>(); //오른쪽 스택 (커서 기준 오른쪽 문자열)

        for(char c : str.toCharArray()) {
            leftSt.push(c); //문자열을 문자 단위로 왼쪽 스택에 넣음
        }

        for(int i = 0; i < M; i++) {
            String command = br.readLine(); //명령어 한 줄을 읽어온다
            char c = command.charAt(0); //명령어의 첫 번째 문자를 가져온다

            switch(c) {
                case 'L': //왼쪽으로 커서 이동
                    if(!leftSt.isEmpty())
                        rightSt.push(leftSt.pop()); //왼쪽에서 오른쪽으로 이동
                    break;
                case 'D': //오른쪽으로 커서 이동
                    if(!rightSt.isEmpty())
                        leftSt.push(rightSt.pop()); //오른쪽에서 왼쪽으로 이동
                    break;
                case 'B': //커서 왼쪽 문자 삭제
                    if(!leftSt.isEmpty()) {
                        leftSt.pop(); //왼쪽 스택에서 문자 삭제
                    }
                    break;
                case 'P': //문자 추가
                    char t = command.charAt(2); //명령어에서 추가할 문자 가져오기
                    leftSt.push(t); //왼쪽 스택에 추가
                    break;
                default:
                    break;
            }
        }

        while(!leftSt.isEmpty()) {
            rightSt.push(leftSt.pop()); //남아있는 모든 문자를 오른쪽 스택으로 옮긴다
        }

        StringBuilder result = new StringBuilder();
        while(!rightSt.isEmpty()) {
            result.append(rightSt.pop()); //오른쪽 스택에서 문자를 꺼내어 결과에 추가
        }
        System.out.println(result.toString());
    }
}