백준 5397. 키로거

www.acmicpc.net/problem/5397

5397번: 키로거

문제제목 : 키로거

문제난이도 : 실버3 / 중

문제유형 : 스택, 구현, 그리디

풀이 시간 : 40분

문제

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

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

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.

입력

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

출력

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

 

코드

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

public class BJ5397 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<String> leftStack = new Stack<String>();
		Stack<String> rightStack = new Stack<String>();
		
		int tc = Integer.parseInt(br.readLine()); 
		
		for (int i = 0; i < tc; i++) {
			String pw = br.readLine();
			String[] pwArray = pw.split("");
			
			for (int j = 0; j < pwArray.length; j++) {
				if (pwArray[j].equals("<")) {
					if (!leftStack.isEmpty()) {
						rightStack.push(leftStack.pop());
					}
				} else if (pwArray[j].equals(">")) {
					if (!rightStack.isEmpty()) {
						leftStack.push(rightStack.pop());
					}
				} else if (pwArray[j].equals("-")) {
					if (!leftStack.isEmpty()) {
						leftStack.pop();
					}
					
				} else {
					leftStack.push(pwArray[j]);
				}
			}
			
			StringBuilder sb = new StringBuilder();
			
			while (!rightStack.isEmpty()) {
				leftStack.push(rightStack.pop());
			}
			
			while (!leftStack.isEmpty()) {
				sb.append(leftStack.pop());
			}
			System.out.println(sb.reverse().toString());
		}
	}
}

 

문자열을 받아서 그 문자열을 배열처럼 쓰고 싶어서 배열을 선언했는데, charAt()라는 것을 사용하면 훨씬 더 편리하다.

 

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

public class BJ5397 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> leftStack = new Stack<Character>();
		Stack<Character> rightStack = new Stack<Character>();
		
		int tc = Integer.parseInt(br.readLine()); 
		
		for (int i = 0; i < tc; i++) {
			String pw = br.readLine();
			//String[] pwArray = pw.split(""); //배열로 주는대신 charAt(i)
			
			for (int j = 0; j < pw.length(); j++) { //String.length() 문자열길이
				if (pw.charAt(j) == '<') {
					if (!leftStack.isEmpty()) {
						rightStack.push(leftStack.pop());
					}
				} else if (pw.charAt(j) == '>') {
					if (!rightStack.isEmpty()) {
						leftStack.push(rightStack.pop());
					}
				} else if (pw.charAt(j) == '-') {
					if (!leftStack.isEmpty()) {
						leftStack.pop();
					}
					
				} else {
					leftStack.push(pw.charAt(j));
				}
			}
			
			StringBuilder sb = new StringBuilder();
			
			while (!rightStack.isEmpty()) {
				leftStack.push(rightStack.pop());
			}
			
			while (!leftStack.isEmpty()) {
				sb.append(leftStack.pop());
			}
			
			System.out.println(sb.reverse().toString());
		}
	}
}

 

아이디어

주의1. 문자열 크기가 최대 100만이므로 시뮬레이션 방식으로는 문제를 해결할 수 없다.

 - 단순히 주어진대로 구현할 수 없다. 적절한 알고리즘을 사용하여 문제를 풀어야한다.

주의2. 스택을 활용하여 선형시간 문제를 해결할 수 있는 알고리즘을 설계한다.

 

1) 스택을 두개 만들고 스택 두 개의 중간 지점을 커서로 간주한다.

 

2) 커서를 왼쪽으로 움직이면 왼쪽스택에서 오른쪽스택으로 이동시킨다.

3) 커서를 오른쪽으로 움직이면 오른쪽 스택에서 왼쪽스택으로 이동시킨다.

4) 지우면 왼쪽스택에서 최상단원소를 삭제한다.

5) 일반 문자 입력은 왼쪽스택에 삽입한다.

6) 마지막으로 비밀번호 출력을 할때, 스택에서 뽑으면 역순이므로 reverse()를 이용하여 원래대로 출력해준다.

 

예외상황

1. 오른쪽 스택에 원소가 남는 경우

[ TC1 : ABCD<< ] [ TC2 : ABCD<<EF ]

추가학습

• String str = "hello"; str.chatAt(0) == 'h';
• String끼리 비교는 equals를 사용하고 char는 == 비교를 사용한다.

 

---

백준에 코드를 제출하면서 주어진 테스트케이스 이외의 테스트케이스를 생각해봐야한다는걸 뼈저리게 느꼈다.

문제를 읽고 알고리즘에 대해 충분히 생각한 후, 예외상황은 없는지 골똘히 생각해보는 습관을 가져야겠다.