[백준] 5397번 키로거 (Java)

백준 5397번 키로거 : https://www.acmicpc.net/problem/5397

5397번: 키로거

 

 

키보드의 입력을 통해 비밀번호를 찾는 문제이다.

처음엔 StringBuilder의 insert 함수를 사용해 중간의 위치에 문자를 삽입하는 방식을 사용했었다.

이런 방식으로 하면 테스트 케이스는 통과하지만 채점 시에 시간 초과가 생기게 된다.

아무래도 insert 함수가 시간이 오래 걸리는 듯했고, 새로운 방식으로 풀어야 했다.

그래서 Stack을 2개 사용해서 cursor를 기준으로 앞에 있는 문자열은 pre Stack에 쌓고 뒤에 있는 문자열은 post Stack에 쌓았다.

그리고 >가 나오면 cursor가 오른쪽으로 한 칸 움직이는 것이므로 post에서 하나 pop() 해서 pre에 쌓았다.

<가 나오면 반대로 pre에서 pop() 한 뒤 post에 쌓았다.

Stack을 사용해서 하니 StringBuilder를 사용해서 하는 것보다 훨씬 깔끔하게 작성이 되었다.

 

 

코드

Stack 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

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

        for (int t = 0; t < T; t++) {
            pwd = br.readLine();

            String password = getPwd(pwd);
            System.out.println(password);
        }
    }

    public static String getPwd(String pwd) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> pre = new Stack<>();
        Stack<Character> post = new Stack<>();

        for (int i = 0; i < pwd.length(); i++) {
            switch (pwd.charAt(i)) {
                case '<':
                    if (!pre.isEmpty()) post.push(pre.pop());
                    break;
                case '>':
                    if (!post.isEmpty()) pre.push(post.pop());
                    break;
                case '-':
                    if (!pre.isEmpty()) pre.pop();
                    break;
                default:
                    pre.push(pwd.charAt(i));
                    break;
            }
        }
        while (!post.isEmpty()) {
            pre.push(post.pop());
        }
        for (int i = 0; i < pre.size(); i++) {
            sb.append(pre.elementAt(i));
        }
        return sb.toString();
    }
}

 

 

StringBuilder 사용 (시간초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        for (int t = 0; t < T; t++) {
            pwd = br.readLine();

            String password = getPwd(pwd);
            System.out.println(password);
        }
    }

    public static String getPwd(String pwd) {
        int len = pwd.length();
        StringBuilder sb = new StringBuilder();
        int cursor = 0;
        for (int i = 0; i < len; i++) {
            switch (pwd.charAt(i)) {
                case '<':
                    if (cursor != 0) cursor--;
                    break;
                case '>':
                    if (sb.length() != cursor) cursor++;
                    break;
                case '-':
                    if (cursor != 0) {
                        cursor--;
                        sb.deleteCharAt(cursor);
                    }
                    break;
                default:
                    sb.insert(cursor, pwd.charAt(i));
                    cursor++;
                    break;
            }
        }
        return sb.toString();
    }
}