백준 5397 키 로거 (JAVA 자바 풀이)

백준 5397 키 로거 (JAVA 자바 풀이)

 

---

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

 

 

---

 

 

💡 풀이 과정

 

커서의 이동에 따라 문자를 삽입, 삭제, 이동하는 과정을 구현하는 문제이다. 

 

linkedlist의 인덱스를 관리하는 방법도 있겠지만 스택 특성을 이용하면 쉽게 풀릴 수 있는 문제이다. 

 

이때 두 개의 스택을 생각해내는 것이 문제 풀이의 핵심 아이디어이다. 

 

하나의 스택에는 커서 왼쪽의 문자들을 저장하고 다른 하나는 커서 오른쪽의 문자들을 저장한다. 무슨 말일까? 문제의 예시를 들어서 살펴보자. 

 

문제에서 주어진 예시는 다음과 같다. 

 

예제 입력 

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

 

예제 출력 

 

BAPC
ThIsIsS3Cr3t

 

 

첫 번째 예시를 보자.

 

1. 먼저 << 두 문자는 왼쪽 화살표이고, 아직 왼쪽 스택에 아무 것도 없기 때문에 아무 일도 일어나지 않는다. 

   - 왼쪽 스택: [], 오른쪽 스택: []

2. B: 그 다음 입력되는 B 문자는 일반 문자이므로 왼쪽 스택에 푸시한다. 
   - 왼쪽 스택: [B], 오른쪽 스택: []

3. P: 마찬가지로 P 문자를 왼쪽 스택에 푸시한다.
   - 왼쪽 스택: [B, P], 오른쪽 스택: []

4. <: 왼쪽 화살표는 왼쪽 스택의 항목을 오른쪽으로 옮긴다. 따라서 P가 오른쪽으로 이동된다.
   - 왼쪽 스택: [B], 오른쪽 스택: [P]

5. A: 일반 문자인 A가 이제 왼쪽에 들어간다.
   - 왼쪽 스택: [B, A], 오른쪽 스택: [P]

6. >>: 두 번의 오른쪽 화살표는 오른쪽 스택의 상단 항목을 왼쪽 스택으로 이동시킨다. 이때 오른쪽 스택에 항목이 하나밖에 없으므로 한 번만 이동시킨다. 따라서 P가 다시 이동된다.
   - 왼쪽 스택: [B, A, P], 오른쪽 스택: []

7. C: 왼쪽 스택에 푸시한다.
   - 왼쪽 스택: [B, A, P, C], 오른쪽 스택: []

8. d: 왼쪽 스택에 푸시한다.
   - 왼쪽 스택: [B, A, P, C, d], 오른쪽 스택: []

9. -: 백스페이스는 왼쪽 스택의 상단 항목을 제거한다.
   - 왼쪽 스택: [B, A, P, C], 오른쪽 스택: []

 

 

여기서 스택을 두 개로 관리하면서 < 와 > 의 이동에 따라서 항목들을 옮김으로써 중간의 삽입 연산을 수행해준다. 즉, 커서의 이동이란 결국 두 글자 사이의 이동이며, 커서와 최근접 위치에서 발생한 지점에서 연산이 발생한다는 점에 따라 두 개의 스택을 통해 이를 구현해 줄 수 있는 것이다. 

 

이를 정리해보면 다음과 같다. 

 

- 문자 입력: 커서 왼쪽 스택에 새 문자를 추가.
- 백스페이스(-): 커서 왼쪽 스택에서 최상단 문자를 제거.
- 왼쪽 화살표(<): 커서를 왼쪽으로 이동시키는데, 이는 커서 왼쪽 스택의 최상단 문자를 오른쪽 스택으로 옮기는 것과 동일.
- 오른쪽 화살표(>): 커서를 오른쪽으로 이동시키는데, 이는 커서 오른쪽 스택의 최상단 문자를 왼쪽 스택으로 옮기는 것과 동일.

 

코드로 보면 다음과 같다. 

 

Deque<Character> leftStack = new LinkedList<>();
Deque<Character> rightStack = new LinkedList<>();

for (char ch : input.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;
   }
}

 

 

이제 왼쪽의 문자들을 연결하여 최종 비밀번호를 연결하면 된다. 스택의 특성상, 문자들은 LIFO 순서로 나타나므로, 최종 출력은 왼쪽 스택의 내용을 역순으로 조합하면 된다. 왜 그럴까?

 

 

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

 

왼쪽 스택에 문자들은 커서 왼쪽에 위치한 문자들이며, 최신에 입력된 문자가 스택의 상단에 있다. 하지만, 우리가 필요로 하는 출력 형태는 입력 순서대로, 즉 스택의 바닥에서부터 시작하는 순서이다. 따라서, 왼쪽 스택의 모든 요소를 오른쪽 스택으로 이동시키는 과정을 거쳐서, 왼쪽 스택의 바닥 요소가 오른쪽 스택의 상단에 위치하게 하고, 그 다음, 오른쪽 스택에서 요소를 꺼낼 때 입력된 순서대로 꺼내면 원하는 문자열이 된다.

 

💡 코드 구현

 

 

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

   private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
      return new StringTokenizer(bufferedReader.readLine());
   }

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

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = receiveInput(bufferedReader);
      int T = parseInt(stringTokenizer.nextToken()); // testCases


      while (T-- > 0) {
         stringTokenizer = receiveInput(bufferedReader);
         String input = stringTokenizer.nextToken();
         System.out.println(findPassword(input));
      }
   }

   private static String findPassword(String input) {
      Deque<Character> leftStack = new LinkedList<>();
      Deque<Character> rightStack = new LinkedList<>();

      for (char ch : input.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 password = new StringBuilder();
      while (!leftStack.isEmpty()) {
         rightStack.push(leftStack.pop());
      }
      while (!rightStack.isEmpty()) {
         password.append(rightStack.pop());
      }

      return password.toString();
   }
}