백준 - 에디터 (실버 2)

시간초과 발생

1. ArrayList 사용 시 

 

-> 데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다.
예를들면 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 4개를 앞으로 한칸씩 이동해야 한다.
삽입과 삭제가 많다면 ArrayList는 비효율적이다.

 

2. LinkedList로 수정

-> ArrayList처럼 재배열할 필요가 없어서 빠르지만

삽입/삭제를 위한 검색 시에는 인덱스를 통해 접근하는 것이 아니기에

최악의 경우는 모든 요소를 다 살펴봐야 하기 때문에 O(N)의 시간이 걸린다

게다가 명령어의 개수 M만큼 반복해야 하므로

O(N*M) = 최대 오천억 번 해야 한다. 

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

class Main{
    //public static void edit(List<String> list, String[] method,
      //                      int pos,int last){

    //}
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String s=br.readLine();

        int pos=s.length();
        List<String> list=new LinkedList<>();
        String[] str=s.split("");

        for(int i=0;i<str.length;i++){
            list.add(str[i]);
        }
        int M=Integer.parseInt(br.readLine());

        for(int i=0;i<M;i++){
            String[] method=br.readLine().split(" ");
            switch(method[0]){
                case "L":
                    if(pos!=0){
                        pos--;
                    }
                    break;
                case "D":
                    if(pos!=list.size()){
                        pos++;
                    }
                    break;
                case "B":
                    if(pos!=0){
                        list.remove(pos-1);
                        pos--;
                    }
                    break;
                case "P":
                    String temp=method[1];
                    list.add(pos,temp);
                    pos++;
            }
            //edit(list,method,pos,last);
        }
        bw.write(String.join("",list)); //list<String> -> string으로
        bw.flush();
        bw.close();
    }
}

 

---

 

기준 거리 1 이내로 연산이 행해져야 하는 문제이기 때문에 모든 연산이 O(1)이어야 한다.

-> ListIterator 사용

 

ListIterator는 Iterator를 상속한 인터페이스다.

Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

단, List에서만 사용가능.

 

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

class Main{
    //public static void edit(List<String> list, String[] method,
      //                      int pos,int last){

    //}
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String s=br.readLine();

        int pos=s.length();
        List<String> list=new LinkedList<>();
        String[] str=s.split("");

        for(int i=0;i<str.length;i++){
            list.add(str[i]);
        }
        int M=Integer.parseInt(br.readLine());
        ListIterator<String> iter=list.listIterator();

        while(iter.hasNext()){ //커서를 맨 뒤로 보내기
            iter.next();
        }
        for(int i=0;i<M;i++){
            String[] method=br.readLine().split(" ");
            switch(method[0]){
                case "L":
                    if(iter.hasPrevious()){ //앞에 존재한다면
                        iter.previous(); //커서 앞으로
                    }
                    break;
                case "D":
                    if(iter.hasNext()){ //뒤에 존재한다면
                        iter.next(); //커서 뒤로
                    }
                    break;
                case "B": //커서 앞 문자열 삭제
                    if(iter.hasPrevious()){
                        iter.previous(); //커서 앞으로 보내고 삭제
                        iter.remove();
                    }
                    break;
                case "P":
                    String temp=method[1];
                    iter.add(temp); //추가하고 커서 건드릴 필요없음
            }
            //edit(list,method,pos,last);
        }
        bw.write(String.join("",list)); //list<String> -> string으로
        bw.flush();
        bw.close();
    }
}

 

 

 

1. ListIterator 생성

ListIterator<String> iter=list.listIterator();

 

2. 추가

iter.add(temp);

 

3. 삭제

iter.remove();

 

4. 앞에 원소 존재하는지 확인 -> 앞으로

if(iter.hasPrevious())
	iter.previous();

5. 뒤에 원소 존재하는지 확인 -> 뒤로

if(iter.hasNext())
	iter.next();

 

 

---

Stack을 이용한 풀이

-> 모든 연산이 O(1)이므로 시간초과가 생기지 않는다.

 

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

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));

        String s = br.readLine();

        Stack<String> left_stack = new Stack<>();
        Stack<String> right_stack = new Stack<>();
        String[] str = s.split("");

        for (int i = 0; i < str.length; i++) {
            left_stack.push(str[i]);
        }
        int M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++) {
            String[] method = br.readLine().split(" ");
            switch (method[0]) {
                case "L":
                    if (!left_stack.isEmpty()) {
                        right_stack.push(left_stack.pop());
                    }
                    break;
                case "D":
                    if (!right_stack.isEmpty()) {
                        left_stack.push(right_stack.pop());
                    }
                    break;
                case "B":
                    if (!left_stack.isEmpty()) {
                        left_stack.pop();
                    }
                    break;
                case "P":
                    String temp = method[1];
                    left_stack.push(temp);
            }
        }
        while (!left_stack.isEmpty()) {
            right_stack.push(left_stack.pop());
        }
        StringBuilder sb = new StringBuilder();
        while (!right_stack.isEmpty()) {
            sb.append(right_stack.pop());
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}