[백준 - 1406] 에디터 .java

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

 

-> 즉 양방향으로 커서를 움직여야함 -> listIterator 

 

listIterator<Character>

 리스트 위에서 양방향(앞/뒤)으로 이동하면서 현재 위치에서 삽입·삭제 가능

 

list.listIterator(list.size())

: 초기엔 커서가 문자열의 맨 끝이라는 문제 조건

 

• L명령

커서를 왼쪽으로 한 칸 이동하려면 왼쪽에 원소가 있는지 확인

-> hasPrevious() 참이면 있는것

-> 있으면 previous()를 호출해서 커서를 한 칸 왼쪽으로 옮기고 그 위치의 문자를 반환

 

• D명령

커서를 오른쪽으로 한 칸 이동하려면 오른쪽에 원소가 있는지 확인

-> hasNext() 참이면 있는 것

->있으면 next()를 호출해서 커서를 한 칸 오른쪽으로 옮기고 그 위치의 문자를 반환

 

• B명령

삭제할 대상인 커서 왼쪽에 글자가 있는지 확인

-> hasPrevious() 참이면 있는 것

-> 있으면 previous()를 호출해서 커서를 한 칸 왼쪽으로 이동시키고 그 위치의 문자(삭제 대상)를 반환

=> remove()를 호출하면 방금 previous()가 가리킨(=반환한) 원소가 리스트에서 삭제됨

=> 이때 커서는 삭제된 위치(왼쪽) 그대로 머무르게 됨

 

 

여기서 헷갈렸던 부분

remove()는 마지막으로 next() 또는 previous()가 반환한 원소를 지울 때만 호출할 수 있는 점이다

방금 iterator가 가리켜서 반환(return)한 노드를 지우는 메서드이기 때문

previous() 없이 바로 remove()를 호출하니까 예외 발생했음

 

 

 

시간초과  1

처음 리스트를 ArrayList로 생성

-> 삽입·삭제를 빠르게 하려면 가 아니라 LinkedList여야함

 

 ArrayList면 remove, add마다 뒤에 있는 원소를 전부 한 칸씩 이동시켜야 해서 O(N) 걸림

 

시간초과 2

마지막 리스트에 들어있는 문자열을 출력할 때 

for(char com: list){
            System.out.print(com);
        }

사용하면 시간 초과

 

->

StringBuilder 의 append를 사용하여 O(1)로 추가하고

한번에 모아서 출력하면 O(n)내로 만들 수 있어 시간 초과가 나지 않음

 

 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Character> list = new LinkedList<>();
        String input = sc.nextLine();

        for(char com: input.toCharArray()) {
            list.add(com);
        }
        int m = sc.nextInt();

        //ListIterator를 리스트 맨 끝 위치에서 생성
        ListIterator<Character> listIterator = list.listIterator(list.size());

        while(m-->0){
            char cmd = sc.next().charAt(0);
            //커서를 왼쪽으로
            if(cmd=='L'){
                if(listIterator.hasPrevious()){
                    listIterator.previous();
                }
            }
            //커서를 오른쪽으로
            else if(cmd=='D'){
                if(listIterator.hasNext()) {
                    if (listIterator.hasNext()) {
                        listIterator.next();
                    }
                }
            }
            //커서 왼쪽 글자 삭제
            else if(cmd=='B'){
                if(listIterator.hasPrevious()){
                    listIterator.previous();
                    listIterator.remove();
                }
            } else if(cmd=='P'){//P 명령 뒤에 나오는 문자를 삽입
                listIterator.add(sc.next().charAt(0));
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char com: list){
            sb.append(com);
        }
        System.out.println(sb);
    }
}

 

 

 

실버 2인거에 비해 시간초과가 여러번 나서 당황했다