[백준] 알고리즘 분류(자료구조,JAVA)1406번, 에디터

문제 링크

1406번: 에디터

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 편집기에는 각 명령어를 수행하여 문자열을 편집합니다.

2. 커서는 처음에 문자열 맨 뒤에서 시작합니다.

3. 편집기 명령이 끝난 뒤에 문자열을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 편집기 명령에 따라 문자열 편집을 진행합니다.

 

3. 편집된 문자열을 결과로 출력합니다.

 

 

시행착오

 

초기에는 StringBuilder를 사용해서 명령어대로 문자열을 수정을 진행하였지만 시간초과가 발생하여 실패하였습니다.

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


public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder str = new StringBuilder(br.readLine());
        int position = str.length();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            String command = st.nextToken();
            if(command.equals("L")){
                position = Math.max(position - 1, 0);
            }else if(command.equals("D")){
                position = Math.min(position + 1, str.length());
            }else if(command.equals("B")){
                if(position == 0)
                    continue;
                str.deleteCharAt(position-1);
                position--;
            }else{
                String s = st.nextToken();
                str.insert(position++,s);
            }
        }
        bw.write(str + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

문자열이 Insert, deleteCharAt 되는 부분에서 시간복잡도를 많이 잡아먹는다고 생각하여 다른 방법을 생각하여

 

두 가지 부분으로 나눌 수 있는 2개의 Stack을 사용하여 문제를 해결하였습니다.

 

편집기 진행.

 

편집을 진행하는 과정속에서 커서 기준 오른쪽과 왼쪽을 나누는 2개의 Stack을 구현하였습니다.

 

예를 들어.

 

a

b

c

d(커서)

e

f

g

LeftStack : abcd

RightStack : gfe

 

명령어 :  'L'

 

a

b

c(커서)

d

e

f

g

LeftStack : abc

RightStack : gfed

LeftStack의 peek() 값 ▶ RightStack의 추가(Add)

 

명령어 :  'D'

 

a

b

c

d

e(커서)

f

g

LeftStack : abcde

RightStack : gf

RightStack의 peek() 값 ▶ LeftStack의 추가(Add)

 

명령어 :  'B'

 

a

b

c(커서)

e

f

g

LeftStack : abc

RightStack : gfe

LeftStack의 peek() 값 제거 : LeftStack pop() 진행!

 

명령어 :  'P $'

a

b

c

d

$(커서)

e

f

g

LeftStack : abcd$

RightStack : gfe

LeftStack의 '$' 추가(Add)

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

문자열 : abcd

 

M = 3

 

명령어

P x

 

L

 

P y

 

2. 편집기 명령에 따라 문자열 편집을 진행합니다.

 

a

b

c

d(커서)

LeftStack : abcd

RightStack : 

 

문자열 편집 진행!

 

명령어 : P x

 

a

b

c

d

x(커서)

LeftStack : abcdx

RightStack : 

 

LeftStack에 'x' 추가(Add)

 

 

명령어 : L

 

a

b

c

d(커서)

x

LeftStack : abcd

RightStack : x

LeftStack의 peek() 값 : x ▶ RightStack의 'x' 추가(Add)

 

명령어 : P y

 

a

b

c

d

y(커서)

x

LeftStack : abcdy

RightStack : x

 

LeftStack에 'y' 추가(Add)

 

 

3. 편집된 문자열을 결과로 출력합니다.

 

LeftStack : abcdy

RightStack : x

 

LeftStack의 값 ▶ RightStack에 이동!

 

a

b

c

d

y

x

RightStack값 순서대로 pop() 진행!

abcdyx을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• LeftStack, RightStack 2가지 Stack을 사용하여 문자열을 탐색하도록 합니다.
• 편집기 명령어에 따라 2개의 Stack의 값들을 변경하여 편집을 진행합니다.
• LeftStack의 값들을 RightStack에 옮겨줍니다.
• RightStack을 순차적으로 pop()하여  BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();
        Stack<Character> leftStack = new Stack<>();	//LeftStack
        Stack<Character> rightStack = new Stack<>();	//RightStack
        //입력된 문자열 LeftStack에 저장
        for(int i=0;i<str.length();i++)
            leftStack.push(str.charAt(i));
        int N = Integer.parseInt(br.readLine());
        //편집 진행!
        for(int i=0;i<N;i++){
            String command = br.readLine();
            char c = command.charAt(0);
            if(c == 'L'){	//명령어 'L'
                if(!leftStack.isEmpty())	//맨 앞이 아닐 때
                    rightStack.add(leftStack.pop());//LeftStack.peek() -> RightStack
            }else if(c == 'D'){	//명령어 'D'
                if(!rightStack.isEmpty())	//맨 뒤가 아닐 때
                    leftStack.add(rightStack.pop());//RightStack.peek() -> LeftStack
            }else if(c == 'B'){	//명령어 'B'
                if(!leftStack.isEmpty())	//맨 앞이 아닐 때
                    leftStack.pop();	//LeftStack Pop!
            }else{	//명령어 'P $'
                char s = command.charAt(2);	//추가할 '$'
                leftStack.add(s);	//LeftStack Add!
            }
        }
        //LeftStack의 값 -> RightStack 추가!
        while(!leftStack.isEmpty())
            rightStack.push(leftStack.pop());
        //RightStack을 순차적으로 pop()하여 BufferedWriter 저장
        while(!rightStack.isEmpty()){
            bw.write(rightStack.pop());
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}