[Java] 5397번. 키로거

문제 링크 

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

---

 

문제 분석

이전에 풀었던 1406번 에디터 문제와 크게 다르지 않다.

동일하게 문자의 삽입과 삭제가 빈번하게 일어나는 문제이므로

LinkedList로 구현한다.

 

구상한 해결 방안은 다음과 같다.

1.

int형 변수를 입력받는다.

2.

입력받은 수 만큼 아래 과정을 반복한다.

3.

문자열을 입력받는다.

4.

<를 입력하면 왼쪽으로 이동, >를 입력하면 오른쪽으로 이동

-를 입력하면 왼쪽의 문자를 삭제, 문자를 입력하면 저장한다.

5.

최종 LinkedList를 문자열로 변환 후 출력한다.

 

모두 1406번에서 구현한 코드이기 때문에 어렵지 않게 구현할 수 있다.

 

---

최종 코드

import java.io.*;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase=Integer.parseInt(reader.readLine());

        for(int i=0;i<testCase;i++){
            String str=reader.readLine();
            LinkedList<Character> list = new LinkedList<>();

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

            for(char ch:str.toCharArray()) {
                switch (ch) {
                    case '<':
                        if (listIterator.hasPrevious()) {
                            listIterator.previous();
                        }
                        break;
                    case '>':
                        if (listIterator.hasNext()) {
                            listIterator.next();
                        }
                        break;
                    case '-':
                        if (listIterator.hasPrevious()) {
                            listIterator.previous();
                            listIterator.remove();
                        }
                        break;
                    default:
                        listIterator.add(ch);
                        break;
                }
            }

            StringBuilder builder = new StringBuilder();
            for(char ch : list){
                builder.append(ch);
            }

            writer.write(builder.toString());
            writer.newLine();
        }

        writer.flush();
        writer.close();
        reader.close();
    }
}

 

---

개선 방안

위 문제를 LinkedList와 ListIterator를 사용하여 해결하였다.

기능 면에서는 정확하게 구현이 되었지만 성능 면에서 개선될 수 있는 방법이 있다.

 

바로 두개의 stack을 사용하는 방안이다.

stack의 주요 연산인 '삽입(push)'과 '삭제('pop')은 O(1)의 시간 복잡도를 가진다.

따라서 두 개의 스택을 사용하면 삽입과 삭제 연산이 빠르게 수행된다.

이는 이동하는데 O(n)시간이 걸리는 LinkedList보다 훨씬 효율적이다.

 

또한, 커서 왼쪽의 문자를 저장하는 변수와 오른쪽의 문자를 저장하는 변수를 사용하면

커서 이동 또한 O(1)의 시간 복잡도로 수행될 수 있다.

 

LinkedList는 또한 두 개의 주소값을 가지고 있기 때문에 메모리를 차지한다는 단점도 있다.

 

하지만, 이번 주차에는 LinkedList를 공부하였고

아직 스택의 개념에 대해서 정확하게 공부하지 않았기 때문에

아래 코드는 그냥 참고로만 하고 읽어보면 좋겠다~ 하고 넘어가겠다.

.

---

참고

 

//stack를 사용한 코드
import java.io.*;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(reader.readLine());

        for (int i = 0; i < testCase; i++) {
            String str = reader.readLine();
            Stack<Character> leftStack = new Stack<>();
            Stack<Character> rightStack = new Stack<>();

            for (char ch : str.toCharArray()) {
                switch (ch) {
                    case '<':
                        if (!leftStack.isEmpty()) {
                            rightStack.push(leftStack.pop());
                        }
                        break;
                    case '>':
                        if (!rightStack.isEmpty()) {
                            leftStack.push(rightStack.pop());
                        }
                        break;
                    case '-':
                        if (!leftStack.isEmpty()) {
                            leftStack.pop();
                        }
                        break;
                    default:
                        leftStack.push(ch);
                        break;
                }
            }

            StringBuilder builder = new StringBuilder();
            while (!leftStack.isEmpty()) {
                rightStack.push(leftStack.pop());
            }
            while (!rightStack.isEmpty()) {
                builder.append(rightStack.pop());
            }

            writer.write(builder.toString());
            writer.newLine();
        }

        writer.flush();
        writer.close();
        reader.close();
    }
}