[백준 Silver 3] 5397 키로거 - Java

문제링크 : https://www.acmicpc.net/problem/5397

5397번: 키로거

 

접근 과정 : 

• 화살표로 인한 인덱스 변화에 주목하면서, 패스워드를 입력하면 된다고 생각
• 자료구조로, 연결리스트나 스택을 사용할 수 있을 것이라 생각
• 최근 ListIterator를 알게되었고, 연결리스트의 탐색에 필요한 비용을 줄여주기에 이를 사용!!
• vs 스택을 사용하는 경우도 비교해보았다.

 

소스 코드 및 결과 : 

package BOJ;

/*
    키로거 
    
    LinkedList + ListIterator
*/

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

public class BOJ5397 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder result = new StringBuilder();

        while (T-- > 0) {
            String input = br.readLine();
            List<Character> inputList = new LinkedList<>();
            ListIterator<Character> inputIter = inputList.listIterator();

            for (int i = 0; i < input.length(); i++) {
                switch (input.charAt(i)) {
                    case '<':
                        if (inputIter.hasPrevious()) {
                            inputIter.previous();
                        }

                        break;
                    case '>':
                        if (inputIter.hasNext()) {
                            inputIter.next();
                        }

                        break;
                    case '-':

                        if (inputIter.hasPrevious()) {
                            inputIter.previous();
                            inputIter.remove();
                        }
                        break;

                    default:

                        inputIter.add(input.charAt(i));
                        break;
                }
            }

            for (char c : inputList) {
                result.append(c);
            }
            result.append("\n");
        }

        System.out.println(result.toString().trim());
    }
}

 

/*
    키로거 
    
    Stack 2개
    (커서를 기준으로 앞부분과 뒷부분을 의미)

*/

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder result = new StringBuilder();

        while (T-- > 0) {
            String input = br.readLine();

            Stack<Character> front = new Stack<>();
            Stack<Character> back = new Stack<>();

            for (int i = 0; i < input.length(); i++) {
                switch (input.charAt(i)) {
                    case '<':

                        if (!front.isEmpty()) {
                            back.add(front.pop());
                        }

                        break;
                    case '>':
                        if (!back.isEmpty()) {
                            front.add(back.pop());
                        }

                        break;
                    case '-':
                        if (!front.isEmpty()) {
                            front.pop();
                        }
                        break;

                    default:
                        front.add(input.charAt(i));

                        break;
                }
            }

           StringBuilder temp = new StringBuilder();

            while (!front.isEmpty()) {
                temp.append(front.pop());
            }
            result.append(temp.reverse());
            while (!back.isEmpty()) {
                result.append(back.pop());
            }
            result.append("\n");

        }

        System.out.println(result.toString().trim());
    }
}

 

 

/*

    키로거 
    
    Deque / Stack
    
*/

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringBuilder result = new StringBuilder();

        while (T-- > 0) {
            String input = br.readLine();

            Deque<Character> front = new LinkedList<>();
            Stack<Character> back = new Stack<>();

            for (int i = 0; i < input.length(); i++) {
                switch (input.charAt(i)) {
                    case '<':

                        if (!front.isEmpty()) {
                            back.add(front.pollLast());
                        }

                        break;
                    case '>':
                        if (!back.isEmpty()) {
                            front.addLast(back.pop());
                        }

                        break;
                    case '-':
                        if (!front.isEmpty()) {
                            front.removeLast();
                        }
                        break;

                    default:
                        front.addLast(input.charAt(i));

                        break;
                }
            }


            while (!front.isEmpty()) {
                result.append(front.pollFirst());
            }
            while (!back.isEmpty()) {
                result.append(back.pop());
            }
            result.append("\n");

        }

        System.out.println(result.toString().trim());
    }
}

 

P.S

LinkedList+ListIterator < Deque + Stack < Stack+Stack 순으로 더 많은 시간을 소비하였다.

ListIterator 를 통해 LinkedList의 탐색 속도를 줄인것이 주요했다.

(LinkedList의 삽입,삭제는 O(1)이지만, 해당 노드를 탐색하는데 O(N)를 필요로 한다.!!!)

 

더 빠른 속도를 보여주는 다름 사람들은 클래스르 새로 만들거나, 배열을 2개 사용해서 인덱스만 관리한 것 같다.