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

처음 시도한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {


    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        List<Character> list = new ArrayList<>();
        for(int i=0; i<s.length(); i++){
            list.add(s.charAt(i));
        }


        int tc = Integer.parseInt(br.readLine());

        int idx=list.size();

        while(tc-- != 0 ){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            if(command.equals("L")){
                if(idx!=0)idx--;

            }else if(command.equals("D")){
                if(idx !=list.size())idx++;

            }else if(command.equals("B")){
                if(idx!=0){
                    idx--;
                    list.remove(idx);
                }
            }else if(command.equals("P")){
                char word = st.nextToken().charAt(0);
                list.add(idx, word);
                idx++;
            }

        }
        String answer="";
        for(char c : list){
            answer += Character.toString(c);
        }

        System.out.println(answer);
    }
}

ArrayList를 사용한 풀이이다.

여기서 문제가 발생하게 되는데 ArrayList는 삽입과 삭제가 일어날 때 O(N)번의 연산을 수행하게 된다.

해당 문제에서는 삽입과 삭제 자료구조를 돌아다니는 조회가 빈번하게 일어난다. 이를 빠르게 해결할 방법을 찾아야한다.

LinkedList의 iterator를 이용하자

에전에 c++로 문제를 풀었을 떄 사용한 방법이다. iter를 구현해서 iter이 가르키는 값을 이용해 값을 가공?하는 방법이다.

package math.순열;  
  
import java.io.*;  
import java.util.*;  
  
public class Practice {  
  
  
    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();  
  
        LinkedList<Character> list = new LinkedList<Character>();  
        for(int i=0; i<s.length(); i++){  
            list.add(s.charAt(i));  
        }  
  
  
        int tc = Integer.parseInt(br.readLine());  
  
        ListIterator<Character> iter = list.listIterator();  
  
        while(iter.hasNext()){// iterator를 이용해서 마지막 커서 위치로 이동시킨다.  
            iter.next();  
        }  
  
        while(tc-- != 0 ){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            String command = st.nextToken();  
  
            if(command.equals("L")){  
                if(iter.hasPrevious()) iter.previous(); //왼쪽으로 이동  
  
            }else if(command.equals("D")){  
                if(iter.hasNext()) iter.next();//오른쪽으로 이동  
  
            }else if(command.equals("B")){  
                if(iter.hasPrevious()){  
                    iter.previous(); //왼쪽으로 이동  
                    iter.remove(); //remove는 previous나 next로 반환된 가장 마지막 요소를 제거한다.  
                    //즉 remove하기 전에 iter을 움직여줘고 바로 삭제해야 원하는 값을 지운다는 뜻  
                }  
            }else if(command.equals("P")){  
                char word = st.nextToken().charAt(0);  
                iter.add(word);  
            }  
  
        }  
  
        for(char c : list){  
            bw.write(Character.toString(c)) ;  
        }  
  
        bw.flush();;  
        bw.close();  
    }  
}

Stack을 이용한 풀이

애초에 List가 아니라 Stack을 이용해서도 가능하다.
Stack은 삽입, 삭제가 O(1)으로 이루어진다. 왼쪽 오른쪽을 나눠서 Stack에 저장하면 된다.

주의

• 커서의 위치는 한 번에 바꿀 수 없다.(3에서 1로 이동, 1에서 끝으로 한 번에 이동)

커서의 위치가 좌우로 1회만 이동한다고 가정했을 때 사용할 수 있는 방안이다.
커서의 왼쪽에 값을 넣어주고 오른쪽 Stack에 값을 거꾸로 넣어주면 된다.

그리고 커서를 왼쪽 이동할 때 왼쪽의 stack에서 값을 뺀 후 오른쪽 Stack에 push해주면 된다!!

import java.io.*;  
import java.util.*;  
  
public class Practice {  
  
  
    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 tc = Integer.parseInt(br.readLine());  
  
        Stack<Character> left = new Stack<>();  
        Stack<Character> right = new Stack<>();  
  
        //값 세팅하기  
        for(int i=0 ;i< s.length(); i++){  
            left.push(s.charAt(i));  
        }  
  
        while(tc-- != 0 ){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            String command = st.nextToken();  
  
            if(command.equals("L")){  
                //왼쪽으로 이동  
                // 왼쪽에서 빼서 오른쪽으로 넣어주기  
                if(!left.isEmpty()){  
                    right.push(left.pop());  
                }  
  
            }else if(command.equals("D")){  
                //오른쪽으로 이동  
                //오른쪽에서 빼서 왼쪽에 넣어주기  
                if(!right.isEmpty()){  
                    left.push(right.pop());  
                }  
  
            }else if(command.equals("B")){  
  
                //왼쪽 문자 삭제하기  
                if(!left.isEmpty())left.pop();  
  
            }else if(command.equals("P")){  
                //삽입 - 왼쪽에 넣으면 된다.  
                char word = st.nextToken().charAt(0);  
                left.push(word);  
            }  
  
        }  
        //왼쪽에 있는 값을 모두 오른쪽에 옮긴 다음에 출력하면 됨  
        StringBuilder sb = new StringBuilder();  
  
        while(!left.isEmpty())  
            right.push(left.pop());  
  
        while(!right.isEmpty())  
            bw.write(right.pop());  
  
        bw.flush();  
        bw.close();  
    }  
}

풀어보면 좋을 연결리스트 문제들!

백준 연결리스트 문제

참고

https://minhamina.tistory.com/17
백준 연결리스트 문제