[JavaScript] 백준 5397번 키로거

이 글은 백준 5397번 키로거를 풀이한다. 코드는 JavaScript로 구현하였다.

문제

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

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

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

입력

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

출력

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

예제 입력 1

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

예제 출력 1

BAPC
ThIsIsS3Cr3t

제한

• 시간: 1초
• 메모리: 256MB

풀이

접근

이 문제를 처음 봤을 때 자바스크립트에서 연결 리스트 문제를 어떤 식으로 풀 수 있을까 고민하다가,

비밀번호를 저장 할 배열 하나와 커서의 역할을 할 cursorPointer 변수를 하나 생성해서 문제를 해결했다.

const keyLoggerArray = [];
let cursorPointer = 0;

그리고 다음 자바스크립트에 배열의 중간 값을 조작할 수 있는 splice() 메서드를 사용하여 값을 추가하고 삭제했다.

array.splice(index, deleteNum)
배열의 index 부터 deleteNum 개 만큼 배열의 요소를 삭제한다.

array.splice(index, deleteNum, insertValue...)
배열의 index 부터 deleteNum 개 만큼 배열의 요소를 삭제하고, insertValue 값(들)을 추가한다.
예를 들어, array.splice(index, 0, 'A') 는 배열의 index에 'A' 라는 문자를 추가한다는 의미이다.

하지만, 이 메소드를 사용해서 문제를 풀면 '시간초과' 로 실패한다.

splice 메소드는 배열을 조작한 후 index를 재정렬하는 과정이 필요한데 이 때 O(n)의 시간복잡도를 가지게 된다.

해당 문제에서 요구하는 시간 제한은 1초이고, L의 최대 문자열 개수는 1,000,000개이기에 최악의 경우 O(n^2)의 시간복잡도를 가지게 되는 것이다.

 

따라서, 다른 방법을 통해 더 효율적인 해결방안을 찾아야 했다.

 

그래서, Front 배열과 Back 배열을 각각 생성한 뒤, 커서의 위치를 기준으로 문자를 분할하고 이동시키는 방식을 사용했다.

이 방법은 'splice()' 메서드를 사용하지 않기 때문에 시간 복잡도가 크게 개선된다.

 

원리는 다음과 같다.

 

커서의 앞에 위치하는 문자들은 모두 Front 배열에 넣고,

커서의 뒤에 위치하는 문자들은 모두 Back 배열에 넣는다.

 

조금 더 이해하기 쉽게 그림으로 살펴보자.

'BP<A>>Cd-' 가 입력 값으로 들어왔다고 가정한다.

이렇게 Front 배열과 Back 배열 사이에 커서가 있다고 가정하고 문제를 풀면 쉽게 해결이 가능하다.

단, 주의할 점은 Back 배열에 값을 넣을 때 unshift() 메서드를 사용해서 맨 앞에 값을 추가하고 있는게 아니라 push() 메서드를 사용해서 값을 추가하고 있기 때문에 꼭 마지막에 Back 배열은 reverse() 메서드를 사용해서 배열을 뒤집어주고 출력해야 한다.

unshift() 메서드를 사용하면 똑같이 배열의 index를 재정렬하는 과정이 필요하기 때문에 시간복잡도가 높아지기 때문에 어쩔 수 없다.

console.log(front.join("") + back.reverse().join(""));

구현

내가 구현한 코드 (실패)

/*
- : 백스페이스
< : 왼쪽으로 커서를 한 칸 옮김
> : 오른쪽으로 커서를 한 칸 옮김
나머지 문자: 비밀번호의 일부
만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.
*/

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().split("\n");

// 입력 값 받기
const T = Number(input.shift()); // 테스트 케이스 개수

// keyLogger 함수
const keyLogger = (keys) => {
  // 필요한 변수 선언
  const keyLoggerArray = [];
  let cursorPointer = 0;
  const keysLength = keys.length;

  for (let i = 0; i < keysLength; i++) {
    const key = keys[i];
    switch (key) {
      case "<":
        if (cursorPointer > 0) cursorPointer--;
        break;
      case ">":
        if (cursorPointer < keyLoggerArray.length) cursorPointer++;
        break;
      case "-":
        if (cursorPointer > 0) {
          cursorPointer--;
          keyLoggerArray.splice(cursorPointer, 1); // 배열 중간에 값 삭제
        }
        break;
      default:
        keyLoggerArray.splice(cursorPointer, 0, key); // 배열 중간에 값 추가
        cursorPointer++;
    }
  }
  console.log(keyLoggerArray.join(""));
};

// 테스트 케이스만큼 반복
input.forEach((input) => {
  keyLogger(input.trim()); // 특수문자 제거 (\r)
});

성공한 코드

/*
- : 백스페이스
< : 왼쪽으로 커서를 한 칸 옮김
> : 오른쪽으로 커서를 한 칸 옮김
나머지 문자: 비밀번호의 일부
만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.
*/

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().split("\n");

// 입력 값 받기
const T = Number(input.shift()); // 테스트 케이스 개수

// keyLogger 함수
const keyLogger = (keys) => {
  // 필요한 변수 선언
  const front = [];
  const back = [];

  for (let i = 0; i < keys.length; i++) {
    const key = keys[i];
    switch (key) {
      case "<":
        if (front.length > 0) back.push(front.pop());
        break;
      case ">":
        if (back.length > 0) front.push(back.pop());
        break;
      case "-":
        if (front.length > 0) front.pop();
        break;
      default:
        front.push(key);
    }
  }
  console.log(front.join("") + back.reverse().join(""));
};

// 테스트 케이스만큼 반복
input.forEach((input) => {
  keyLogger(input.trim()); // 특수문자 제거 (\r)
});