Develope Story

2018-07-11 [JAVA] 백준 1406번 - 에디터

11 Jul 2018 | java algorithm_study

문제 출처

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

풀이법

  • cursor의 위치를 파악하여 string의 concat, substring을 활용
import java.util.Scanner;

public class Baekjoon_1406 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        int n = sc.nextInt();
        int cursor = str.length();
        String tmp, input;
        char ch;

        for (int i = 0; i < n; i++) {
            input = sc.next();
            ch =input.charAt(0);
            if (ch == 'L') {
                if (cursor > 0)
                    cursor = cursor-1;
            } else if (ch == 'D') {
                if (cursor < str.length())
                    cursor = cursor+1;
            } else if (ch== 'B') {
                if (cursor == 0) { //커서가 맨 앞일 때
                } else if (cursor == str.length()) { //문자열 끝에 커서
                    str = str.substring(0, str.length() - 1);
                    cursor  =cursor-1;
                } else {
                    tmp = str.substring(0, cursor - 1);
                    str = tmp.concat(str.substring(cursor));
                    cursor  =cursor-1;
                }
            } else if (ch == 'P') {
                input = sc.next();
                if (cursor == 0) { //커서가 맨 앞일 때
                    str = input.concat(str);
                    cursor  =cursor+1;
                } else if (str.length() == cursor) { //문자열 끝에 커서
                    cursor  =cursor+1;
                    str = str.concat(input);
                } else {
                    tmp = str.substring(0, cursor);
                    tmp = tmp.concat(input);
                    str = tmp.concat(str.substring(cursor));
                    cursor  =cursor+1;
                }
            }
        }
        System.out.println(str);
    }
}

=> 메모리 초과

풀이법

  • stackA, stackB 두 개의 스택을 이용하여 문제해결
  • 커서를 기준으로 왼쪽은 stackA 오른쪽은 stackB (코드 상은 StackA = st, StackB = st_tmp)
  • L => 커서 왼쪽으로 이동시 stackA의 top -> stackB
  • D => 커서 왼쪽으로 이동시 stackB의 top -> stackA
  • P => 커서 왼쪽에 입력 stackA에 push
  • B => 커서의 왼쪽 삭제 stackA pop으로 삭제

스택 활용

import java.util.Scanner;
import java.util.Stack;

public class Baekjoon_1406 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        int n = sc.nextInt();
        String input;

        Stack<Character> st = new Stack<>();
        Stack<Character> st_tmp = new Stack();

        for (int i=0; i< str.length(); i++){
            st.push(str.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            input = sc.next();
            if (input.charAt(0) == 'L') { //커서 왼쪽이동
                if(!st.empty())
                    st_tmp.push(st.pop());
            } else if (input.charAt(0) == 'D') { //커서 오른쪽이동
                if(!st_tmp.isEmpty()){
                    st.push(st_tmp.pop());
                }
            } else if (input.charAt(0)== 'B') { //커서 왼쪽 삭제
                if(!st.isEmpty()){
                    st.pop();
                }
            } else if (input.charAt(0) == 'P') { //커서 왼쪽 입력
                input = sc.next();
                st.push(input.charAt(0));
            }
        }
//출력
        while (!st.isEmpty()){ //stack의 LIFO 성질 때문에 stack_tmp에 이동후 출력
            st_tmp.push(st.pop());
        }
        while (!st_tmp.isEmpty()){
            System.out.print(st_tmp.pop());
        }
        System.out.println();
    }
}

=> 메모리 초과

풀이

  • Scanner 대신 BufferedReader 사용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

public class Baekjoon_1406 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str = br.readLine();
        int n = Integer.parseInt(br.readLine());
        String input;

        Stack<Character> st = new Stack<>();
        Stack<Character> st_tmp = new Stack();

        for (int i=0; i< str.length(); i++){
            st.push(str.charAt(i));
        }

        for (int i = 0; i < n; i++) {
            input = br.readLine();
            if (input.charAt(0) == 'L') {
                if(!st.empty())
                    st_tmp.push(st.pop());
            } else if (input.charAt(0) == 'D') {
                if(!st_tmp.isEmpty()){
                    st.push(st_tmp.pop());
                }
            } else if (input.charAt(0)== 'B') {
                if(!st.isEmpty()){
                    st.pop();
                }
            } else if (input.charAt(0) == 'P') 
                st.push(input.charAt(2));
            
        }

        while (!st.isEmpty()){
            st_tmp.push(st.pop());
        }
        while (!st_tmp.isEmpty()){
            System.out.print(st_tmp.pop());
        }
        System.out.println();
    }
}

=> 해결

Related Posts

Comments