[BOJ 5397번/Stack, LinkedList] 키로거 (Java)

문제 링크

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

5397번: 키로거

백준 5397번 키로거는 실제로 키보드로 입력된 문자열을 기록하여, 키를 누르거나 뗄 때마다 키 입력 상태가 바뀌는 상황에서 입력된 문자열을 출력하는 문제이다.

 

풀이방법

1) Stack을 이용한 방법

 - Stack을 통한 문제해결 동작 방식

1. 문자열 입력 받기 및 Stack 선언(leftStack, rightStack)
   • 입력 받은 문자열을 String으로 저장합니다.
   • 커서를 기준으로 왼쪽과 오른쪽 스택을 각각 생성한다. (leftStack, rightStack)
2. Stack을 이용한 키 로거 실행
   • 문자열을 처음부터 끝까지 반복하면서, 문자를 하나씩 읽어들인다.
   • 만약 읽은 문자가 '<'인 경우, leftStack이 비어있지 않으면 leftStack에서 하나의 문자를 pop하여 rightStack에 push한다.
   • 만약 읽은 문자가 '>'인 경우, rightStack이 비어있지 않으면 rightStack에서 하나의 문자를 pop하여 leftStack에 push 한다.
   • 만약 읽은 문자가 '-'인 경우, leftStack이 비어있지 않으면 leftStack에서 하나의 문자를 pop한다.
   • 그 외의 문자인 경우, leftStack에 문자를 push한다.
3. Stack에 남은 문자열 출력
   • Stack에 남은 문자열을 출력합니다. 단, Stack의 구조는 LIFO(Last In First Out)이므로 문자열을 역순으로 출력하면 된다.

 - Stack을 이용한 문제해결 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            Stack<Character> left = new Stack<>();
            Stack<Character> right = new Stack<>();
            String input = br.readLine();

            for(char ch : input.toCharArray()) {
                switch(ch) {
                    case '<':
                        if(!left.empty()) {
                            right.push(left.pop());
                        }
                        break;
                    case '>':
                        if(!right.empty()) {
                            left.push(right.pop());
                        }
                        break;
                    case '-':
                        if(!left.empty()) {
                            left.pop();
                        }
                        break;
                    default:
                        left.push(ch);
                        break;
                }
            }

            StringBuilder sb = new StringBuilder();
            while(!left.empty()) {
                right.push(left.pop());
            }
            while(!right.empty()) {
                sb.append(right.pop());
            }
            System.out.println(sb.toString());
        }
    }
}

 

 - 시간복잡도와 공간복잡도

이러한 방식으로 구현하면, 입력 문자열을 한번만 탐색하므로 시간복잡도는 O(N)이다. 하지만, 저장공간을 leftStack과 rightStack 두개를 사용하게 된다.

 

 

2) LinkedList을 이용한 방법

 - LinkedList를 통한 문제해결 동작 방식

1. LinkedList 및 커서의 위치를 가리키는 변수 선언
   
   • 입력 받은 문자열을 String으로 저장합니다.
   • LinkedList와 커서의 위치를 가리키는 *Listlterator를 선언.
     * ListIterator는 List 인터페이스의 구현체에서 요소를 순차적으로 읽거나, 추가, 수정, 삭제할 수 있는 양방향 반복자입니다.
2. LinkedList를 이용해 키로거 실행
   
   • '<' : 만약 커서가 맨 앞이 아니면 커서를 왼쪽으로 이동한다.
   • '>' : 만약 커서가 맨 끝이 아니면 커서를 오른쪽으로 이동한다.
   • '-' : 만약 커서가 맨 앞이 아니면, 커서가 위치한 노드의 이전 노드와 다음 노드를 서로 연결한다.
   • 문자 : 문자를 입력받은 리스트에 삽입하고, 커서가 위치한 노드의 이전 노드와 새로운 노드를 연결하고, 새로운 노드와 다음 노드를 연결한다.
3. 리스트의 요소를 출력한다.
   
   

 - LinkedList을 이용한 문제해결 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            String input = br.readLine();
            LinkedList<Character> list = new LinkedList<>();
            ListIterator<Character> iter = list.listIterator();

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

            StringBuilder sb = new StringBuilder();
            for (char c : list) {
                sb.append(c);
            }
            System.out.println(sb.toString());
        }

        br.close();
    }
}

 - 시간복잡도와 공간복잡도

Stack을 통해 구현한 방법과 마찬가지로 동일한 시간복잡도를 갖는다. 하지만 커서를 저장하기 위한 저장공간을 더 사용하게 된다.

 

 

 

두 풀이 방법의 비교

1) 시간복잡도와 공간복잡도

 - 두 풀이 방법 모두 동일한 O(n)의 시간복잡도를 갖는다.
 - Stack 풀이는 Stack을 두개 사용해야하고, LinkedList는 커서를 저장하기 위한 공간을 사용하게 된다.
   => Stack을 사용하는 코드가 공간복잡도가 조금 더 높을 것으로 예상된다.

 

2) 코드 복잡도 및 가독성

• Stack: 스택 두 개를 사용해야 하므로 코드가 다소 복잡해질 수 있지만, 커서를 관리할 필요가 없다.
• LinkedList: 커서를 사용해 리스트의 원소를 직접 조작해야 하므로 코드가 다소 복잡해질 수 있다.