[백준] 5397. 키로거 (JAVA)

이번에 풀어 볼 문제는 <백준 5397번.  키로거>이다.

https://www.acmicpc.net/problem/5397

📌 문제 탐색하기

목표

강산이의 비밀번호 알아내기

해야 할 것

1. 강산이가 입력한 문자열을 보고 규칙 적용하기

2. 최종 문자열 출력

입력

[첫줄] 테스트 케이스의 수 

[둘째줄 ~ ] 강산이가 입력한 문자열 ( 1 ≤ L (문자열의 길이) ≤ 10^6 )

 

아이디어

1. 적용해야 할 규칙

'-' : 백스페이스 , 현재 커서 위치의 왼쪽에 글자가 존재한다면 그 글자를 지운다.

'<' : 커서의 위치를 왼쪽으로 한 칸 움직인다.

'>' : 커서의 위치를 오른쪽으로 한 칸 움직인다.

 

2. 문자열을 어떻게 저장해야 할까?

일단 문자열의 크기가 계속 변하기 때문에 동적 자료형이어야 한다.

삽입, 삭제가 빈번하므로 LinkedList  또는 Stack을 사용해서 풀어보자.

📌 코드 설계하기

1. input을 받고 문자열을 배열 형태로 저장한다.

2. 정답 password를 저장할 LinkedList를 선언하고, 현재 커서의 위치를 ListIterator 를 활용해서 저장한다.

3. input 문자열을 순회하며 규칙에 맞게 ListIterator의 커서를 이동시키고 값을 수정한다.

4. 모든 문자열 순회가 끝나면 남은 문자열을 반환한다.

 

📌 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); // 테스트케이스의 수

        for (int i = 0; i < n; i++) {

            // 입력받은 문자열
            char[] input = br.readLine().toCharArray();

            // 패스워드를 저장할 LinkedList
            LinkedList<Character> password = new LinkedList<>();
            ListIterator<Character> iterator = password.listIterator(0);

            for (char commend : input){
                if(commend == '-' ){
                    if(iterator.hasPrevious()){
                        iterator.previous();
                        iterator.remove();
                    }
                }else if(commend == '<'){
                    if (iterator.hasPrevious()){
                        iterator.previous();
                    }
                }else if (commend == '>'){
                    if (iterator.hasNext()){
                        iterator.next();
                    }
                }else{
                    iterator.add(commend);
                }
            }

            for (char c : password){
                sb.append(c);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

➡️ ListIterator를 활용해서 접근하면 커서 이동, 삽입, 삭제 연산이 O(1)의 시간 내로 수행 가능하다.

➡️ 따라서 최대 연산량은 테스트케이스의 수 * 문자열의 최대 길이 (10^6) 이 될 것이다. 

➡️ 이 문제에서는 테스트 케이스의 범위가 주어지지 않았지만, 이런 경우 테스트 케이스 수가 문제 풀이에 영향을 끼치지 않는다고 가정하고 풀면 될 것 같다. 제한 시간 1초 내에 10^6 번의 연산은 충분히 가능하므로 시간 내에 통과 가능했다.

 

📌 알게 된 것

ListIterator를 쓸 때 hasPrevious() 나 hasNext() 로 예외 상황 잘 처리하는 것 잊지 말기

 

이 문제도 1406. 에디터 문제와 마찬가지로 Stack 으로도 구현 가능했다.

커서를 기준으로 왼쪽에 오는 문자들은 왼쪽 스택에 오른쪽에 오는 문자들은 오른쪽 스택에 저장하면 된다.

 

아래는 Stack으로 구현한 코드이다.

import java.io.*;
import java.util.Stack;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int i=0; i<n; i++){
            char[] input = br.readLine().toCharArray();

            Stack<Character> leftStack = new Stack<>();
            Stack<Character> rightStack = new Stack<>();

            for(char command : input){
                if (command=='-'){
                    if(!leftStack.isEmpty()){
                        leftStack.pop();
                    }
                }else if (command == '<'){
                    if(!leftStack.isEmpty()){
                       rightStack.push(leftStack.pop());
                    }
                }else if (command == '>'){
                    if(!rightStack.isEmpty()){
                        leftStack.push(rightStack.pop());
                    }
                }else{
                    leftStack.push(command);
                }

            }

            while(!leftStack.isEmpty()){
                rightStack.push(leftStack.pop());
            }

            while(!rightStack.isEmpty()){
                bw.write(rightStack.pop());
            }

            bw.write("\n");

        }

        bw.flush();

    }
}