[알고리즘 / 백준] 5397 - 키로거

문제는 위와 같으며 처음에는 커서의 위치를 변수로 가지고 있고 화살표 입력 등에 따라 커서를 이동시키면서 비밀번호를 찾는 방식을 사용하였습니다. 하지만 이렇게 한 경우에는 시간 초과가 발생하였습니다. 그래서 커서를 이동시키지 않고 커서를 기준으로 왼쪽 문자를 담는 배열과 오른쪽 문자를 담는 배열을 따로 선언하는 방식으로 구현하였습니다.

 

파이썬 코드는 아래와 같습니다.

from sys import stdin

test_case = int(stdin.readline())

for _ in range(test_case):
    L = stdin.readline().strip()
    left = []
    right = []

    for ch in L:
        if ch == '<':
            if left:
                right.append(left.pop())  # 커서를 왼쪽으로 이동 시 left 리스트의 마지막 문자를 빼서 right 리스트의 마지막에 추가
        elif ch == '>':
            if right:
                left.append(right.pop())  # 커서를 오른쪽으로 이동 시 right 리스트의 마지막 문자를 빼서 left 리스트의 마지막에 추가
        elif ch == '-':
            if left:
                left.pop()  # 백스페이스의 경우 left 리스트의 마지막 문자를 제거
        else:
            left.append(ch)  # 문자를 추가하는 경우는 left 리스트의 마지막에 추가
    left.extend(reversed(right))  # 최종적으로 문자를 합칠 때 right 리스트의 경우 뒤집어서 left 리스트 뒤로 붙이기
    print(''.join(left))

 

자바 코드는 다음과 같습니다. List 로 구현하고 그대로 for 문을 돌면서 출력을 할때는 시간 초과 등이 발생하여 제공되는 Deque 와 Stringbuilder 를 통해서 구현하였습니다.

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 testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            String L = br.readLine();
            System.out.println(findPassword(L));
        }
    }

    private static String findPassword(String L) {
        Deque<Character> left = new ArrayDeque<>();
        Deque<Character> right = new ArrayDeque<>();

        for (int index = 0; index < L.length(); index++) {
            switch (L.charAt(index)) {
                case '<':
                    if (!left.isEmpty()) {
                        right.addFirst(left.pollLast());
                    }
                    break;
                case '>':
                    if (!right.isEmpty()) {
                        left.addLast(right.pollFirst());
                    }
                    break;
                case '-':
                    if (!left.isEmpty()) {
                        left.pollLast();
                    }
                    break;
                default:
                    left.add(L.charAt(index));
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();

        while (!left.isEmpty()) {
            sb.append(left.pollFirst());
        }

        while (!right.isEmpty()) {
            sb.append(right.pollFirst());
        }

        return sb.toString();
    }
}