[C++, python] 백준 5397번 풀이 ( 키로거 )

- 문제 ( 5397번 ) : 키로거

• 링크 : https://www.acmicpc.net/problem/5397

• 사용자가 비밀번호를 입력할때의 누른 명령을 보고 정확한 비밀번호를 알아내는 프로그램 작성
  이때 정확한 비밀번호는 숫자 및 알파벳 대소문자로만 이루어져있다.

  • 입력은 크게 4가지를 받을 수 있다.
    1) "-" : backspace == 커서 바로 앞에 글자가 있다면 그 글자 삭제
    2) "<" : 왼쪽 화살표 == 커서를 움직일 수 있다면 왼쪽으로 1만큼 이동
    3) ">" : 오른쪽 화살표 == 커서를 움직일 수 있다면 오른쪽으로 1만큼 이동
    4) 숫자 및 알파벳 대소문자 == 비밀번호의 일부

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 testcase 의 개수 입력.
• 둘째 줄부터 길이가 L 인 문자열 입력. ( 이 문자열은 사용자가 입력한 모든 명령 )

[ 출력 ]

• 각 testcase 에 대해서 알아낸 비밀번호 출력.
  ( 비밀번호의 길이는 항상 0보다 크다. )

---

- 문제 풀이

• 이번 문제는 알고리즘 자체는 간단하지만 어떠한 자료구조를 사용할 것인지에 대한 선택의 폭이 넓은 문제다.

  나는 이번 문제를 풀 때 c++ 은 STL 에 있는 list 를 사용해 해결했고, python 은 두개의 stack 을 사용해 해결했다.

1. C++ 구현 방법

• 먼저 c++ 의 해결방법은 간단하지만, list 의 사용법을 잘 알지 못한다면 조금은 애를 먹는 방법이다.
  c++ 의 list 는 linked list 로 구현되어있으므로, 이번 문제를 풀기 좋은 자료구조이다.
  문제를 해결할 때 사용한 기능은 다음과 같다.

  • list 의 iterator : list 순회를 위해 사용
  • list.begin() : list 의 가장 처음 위치
  • list.end() : list 의 가장 처음 위치
  • list.erase(iter) : 현재 iterator 가 가리키고 있는 위치의 원소 삭제
  • list.insert(iter, c) : 현재 iterator 가 가리키고 있는 위치에 원소 c 삽입
  • list.clear() : list 의 모든 원소 삭제

  [ 참고 : https://blockdmask.tistory.com/76 ]

  위의 기능들을 사용해서 문제에 주어진 조건에 맞춰 구현했다.

  1. "-" : backspace
     ⇒ cursor 의 위치가 처음위치가 아니면 현재 iterator 가 있는 부분의 원소 제거
  2. "<" : 왼쪽 화살표 == 커서를 움직일 수 있다면 왼쪽으로 1만큼 이동
     ⇒ cursor 의 위치가 처음위치가 아니면 cursor 의 왼쪽에도 문자가 있다는 것이므로 cursor 의 위치를 1 감소 ( = 왼쪽으로 이동 )
  3. ">" : 오른쪽 화살표 == 커서를 움직일 수 있다면 오른쪽으로 1만큼 이동
     ⇒ cursor 의 위치가 마지막위치가 아니면 cursor 의 오른쪽에도 문자가 있다는 것이므로 cursor 의 위치를 1 증가 ( = 오른쪽으로 이동 )
  4. 숫자 및 알파벳 대소문자 == 비밀번호의 일부
     ⇒ 현재 cursor 의 위치에 입력받은 문자 삽입

2. python 구현방법

• python 의 경우 두개의 stack 을 사용해서 구현했다.
  cursor 를 기준으로 왼쪽에 있는 문자를 저장할 stack 하나, 오른쪽에 있는 문자를 저장할 stack 하나, 총 두개의 stack 을 사용해 구현했다.

  python 으로 구현 시 아래와 같은 방법으로 구현했다.

  1. "-" : backspace
     ⇒ 왼쪽 문자가 저장되어있는 stack이 비어있지 않다면 cursor 기준 왼쪽에 문자가 있다는 것이므로 왼쪽 문자가 저장되어있는 stack 에서 원소 하나 pop
  2. "<" : 왼쪽 화살표 == 커서를 움직일 수 있다면 왼쪽으로 1만큼 이동
     ⇒ 왼쪽 문자가 저장되어있는 stack이 비어있지 않다면 cursor 기준 왼쪽에 문자가 있다는 것이므로 왼쪽 stack 의 top 에 있는 원소를 pop 해서 오른쪽 stack 에 append
     ( == 커서를 왼쪽으로 옮긴 것과 동일 )
  3. ">" : 오른쪽 화살표 == 커서를 움직일 수 있다면 오른쪽으로 1만큼 이동
     ⇒ 오른쪽 문자가 저장되어있는 stack이 비어있지 않다면 cursor 기준 오른쪽에 문자가 있다는 것이므로 오른쪽 stack 의 top 에 있는 원소를 pop 해서 왼쪽 stack 에 append
     ( == 커서를 오른쪽으로 옮긴 것과 동일 )
  4. 숫자 및 알파벳 대소문자 == 비밀번호의 일부
     ⇒ 왼쪽 stack 에 현재 입력받은 문자 append

  그 후 두개의 stack 을 합쳐 하나의 password 를 출력해야하는데, 이때 주의해야할 점은 오른쪽 stack 은 순서가 반대로 되어있기 때문에 반대로 출력해야한다.

  나는 왼쪽 stack 에 오른쪽 원소를 붙이는 방식으로 했으므로, 먼저 오른쪽 stack 을 reverse 함수를 사용해 순서를 변경하고, list 의 extend 함수를 사용해서 오른쪽 stack 의 원소를 왼쪽 stack 에 append 해주었다.

  그 후 join 함수를 사용해서 왼쪽 stack 을 출력해주었다.

---

- 최종 코드

• c++ code

#include <iostream>
#include <list>
#include <string>
using namespace std;

// list of password key
list<char> password;

// get correct password
void get_correct_key(string pwd) {
  list<char>::iterator cursor = password.begin();
  
  for(char c : pwd) {
    switch(c){
      // backspace
      case '-':
        // check cursor is at the beginning
        if(cursor != password.begin()) {
          cursor = password.erase(--cursor);
        }
        break;

      // left arrow
      case '<':
        // check cursor is at the beginning
        if(cursor != password.begin()) {
          cursor--;
        }
        break;

      // right arrow
      case '>':
        // check cursor is at the end
        if(cursor != password.end()) {
          cursor++;
        }
        break;

      // numbers and letters
      default:
        password.insert(cursor, c);
    }
  }
}

// print password (list -> string)
void print_password() {
  for(char key : password) {
    cout << key;
  }
  cout << endl;
}

int main() {
  // input # of testcase
  int testcase = 0;
  cin >> testcase;

  // store input password
  string input_pwd = "";

  // execute #testcase times
  for(int i = 0; i < testcase; i++) {
    // input password
    cin >> input_pwd;

    // initialize password list
    password.clear();

    // get password
    get_correct_key(input_pwd);
  
    // print result
    print_password();
  }
  
  return 0;
}

• python code

# input n (execute times)
n = int(input())

# execute n times
for _ in range(n):
  leftside = [] # left of cursor
  rightside = [] # right of cursor

  password = input()
  for c in password:
    # backspace : pop from left stack
    if c == '-': 
      # check cursor is at the beginning
      if(leftside):
        leftside.pop()

    # left arrow : move char left stack to right stack
    elif c == '<': 
      if(leftside): # check leftside is empty
        rightside.append(leftside.pop())

    # right arrow : move char right stack to left stack
    elif c == '>':
      if(rightside): # check rightside is empty
        leftside.append(rightside.pop())

    # number or letter : add left stack 
    else:
      leftside.append(c)

  leftside.extend(reversed(rightside))
  print(''.join(leftside))