[백준] 1406번 에디터 _ JAVA ( 주석 설명 )

풀이

 * 초기 문자열을 넣을 자료구조 : LinkedList

Why?

'커서' 를 중심으로 push, pop을 해야 하므로, LinkedList를 사용하였다.

연결구조로 각 요소가 이전과 다음 요소의 정보를 가지고 있어, 해당 정보를 활용하여 push, pop을 하기에 용이하다고 생각



1) 커서의 위치를 str.length()로 설정한다.


2) L, D 명령마다 커서의 위치를 이동시킨다.


3) B 커서의 위치를 왼쪽으로 이동시키고 삭제를 한다.

- 이 때 커서의 위치가 맨 앞이었을 경우, 커서의 위치가 음수가 되므로 0으로 초기화 및 삭제를 하지 않는다.


4) P : 커서의 위치에 문자를 추가하고, 커서의 위치를 오른쪽으로 이동시킨다.


5) LinkedList의 list.get()으로 StringBuilder에 넣어 남은 원소를 출력한다.

 

코드

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


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

        String str = br.readLine(); //초기 편집기에 입력된 문자열

        //초기 문자열 넣을 자료구조
        //'커서'를 중심으로 push, pop을 해야하므로, 연결구조를 사용하였다.
        LinkedList<Character> sentence = new LinkedList<>();
        for(int i=0;i<str.length();++i){
            sentence.addLast(str.charAt(i));
        }

        int cursor = str.length(); //커서의 위치

        int M = Integer.parseInt(br.readLine()); //명령어의 개수
        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            switch (command){
                case "L":
                    cursor--;
                    if(cursor<0) //커서가 문장의 맨 앞이면
                        cursor = 0;
                    break;

                case "D":
                    cursor++;
                    //현재 문장의 맨 뒤이므로 sentence.size()이다.
                    //str.length() x
                    if(cursor>sentence.size()) //커서가 문장의 맨 뒤면
                        cursor = sentence.size();
                    break;

                case "B":
                    cursor--;
                    if(cursor<0) { //커서가 이미 문장의 맨 앞이면 삭제할 게 없음 => break
                        cursor = 0; //커서 위치 유지
                        break;
                    }
                    else{
                        sentence.remove(cursor); //해당 위치 문자 삭제
                    }
                    break;

                case "P":
                    Character add = st.nextToken().charAt(0); //추가할 문자

                    sentence.add(cursor, add);
                    cursor++; //<문자가 추가됐으므로, 커서가 오른쪽으로 한 칸 이동>
            }
        }

        //LinkedList 형태로 바로 출력하면 list [] 형태로 나옴
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<sentence.size();++i){
            sb.append(sentence.get(i));
        }
        System.out.println(sb);
    }
}

 

But. push/pop 시 해당 인덱스에 바로 접근하는 것이 아니라,
head와 tail을 제외하고 하나하나 살펴보며 처리해야 하기 때문에 실행 시간이 늘어난다.

 

---

https://minhamina.tistory.com/17

풀이

→ 따라서 LinkedList의 반복자 listiterator 를 커서로 같이 사용해, 선택적으로 push/pop 이 가능하게끔 구현했다.

(iterator 과 달리, List Collection의 요소들을 양방향에서 접근이 가능하다.)

 

리턴 타입	메소드	설명
void	add(E e)	해당 리스트(list)에 전달된 요소를 추가함. (선택적 기능)
boolean	hasNext()	이 리스트 반복자가 해당 리스트를 순방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함.
boolean	hasPrevious()	이 리스트 반복자가 해당 리스트를 역방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함.
E	next()	리스트의 다음 요소를 반환하고, 커서(cursor)의 위치를 순방향으로 이동시킴.
E	previous()	리스트의 이전 요소를 반환하고, 커서(cursor)의 위치를 역방향으로 이동시킴.
void	remove()	next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 리스트에서 제거함. (선택적 기능)

 

코드

//BufferedWriter 대신 StringBuilder 사용
//BufferedWriter 가 메모리, 실행속도에서 더 효율적이다.
//명령어 처리할 때 String으로 한 번에 받고 charAt 으로 부분적으로 받아서 처리

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

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

        String str = br.readLine(); //초기 편집기에 입력된 문자열

        //초기 문자열 넣을 자료구조
        //'커서'를 중심으로 push, pop을 해야하므로, 연결구조를 사용하였다.
        LinkedList<Character> sentence = new LinkedList<>();
        for(int i=0;i<str.length();++i){
            sentence.add(str.charAt(i));
        }


        int M = Integer.parseInt(br.readLine()); //명령어의 개수

        ListIterator<Character> listIterator = sentence.listIterator();

        while (listIterator.hasNext()){
            //iter.next() : 리스트의 다음 요소를 반환하고, 커서의 위치를 순방향으로 이동시킴
            listIterator.next(); //커서의 위치를 맨 뒤로 보내줌
        }


        for(int i=0;i<M;++i){
            String com = br.readLine();
            char command = com.charAt(0);
            switch (command){
                case 'L':
                    if(listIterator.hasPrevious())
                        listIterator.previous();
                    break;

                case 'D':
                    if(listIterator.hasNext())
                        listIterator.next();
                    break;

                case 'B':
                    //커서가 맨 처음이 아니라면
                    if(listIterator.hasPrevious()) {
                        listIterator.previous();
                        listIterator.remove();
                    }
                    break;

                case 'P':
                    Character plus = com.charAt(2); //추가할 문자

                    //<해당 커서 공간에 add, 커서의 위치를 순방향으로 이동>
                    listIterator.add(plus);
            }
        }

        //LinkedList 형태로 바로 출력하면 list [] 형태로 나옴
        StringBuilder sb = new StringBuilder();
        for(Character c : sentence){
            sb.append(c);
        }
        System.out.println(sb);
    }
}

BufferedWriter 를 이용한 출력