[백준/boj] 5397: 키로거 (Java) / Deque

문제

풀이

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws IOException {
		int T = stoi(br.readLine());
		for (int i = 0; i < T; i++) {
			Deque<Character> pw = new ArrayDeque<Character>();
			Deque<Character> wait = new ArrayDeque<Character>();

			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < ch.length; j++) {
				char c = ch[j];
				if (c == '<' || c == '>' || c == '-') {
					switch (c) {
					case '<': {
						if (pw.isEmpty())
							break;
						wait.addFirst(pw.removeLast());
						break;
					}
					case '>': {
						if (wait.isEmpty())
							break;
						pw.addLast(wait.removeFirst());
						break;
					}
					case '-':
						if(pw.isEmpty()) break; // *** 
						pw.removeLast();
						break;
					}
				} else {
					pw.addLast(c);
				}
			}
			
			while (!wait.isEmpty())
				pw.addLast(wait.removeFirst());
			while (!pw.isEmpty())
				bw.append(pw.removeFirst()+"");
			bw.append("\n");
		}
		bw.flush();
		bw.close();
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

 

 

두개의 Deque(덱)을 이용해 풀었다. Deque의 가장 큰 특징은 앞, 뒤로 요소를 삽입/ 제거 할 수 있다는 점이다.

pw 덱과 wait 덱에는 <>- 와 같은 입력이 아닌 비밀번호가 될 수 있는 값들만 삽입/ 제거하도록 했다.

 

A<B>c- 가 입력 되는 경우를 살펴보자.

 

A

먼저 < > - 가 아닌 경우(A)에는 pw Deque 에 무조건 삽입한다 (뒤로!) 

이때, 커서는 A 옆에 위치하게 된다.

 

A<

 

< 가 입력 되었을 땐 pw 덱이 비어있으면 커서가 이동할 필요가 없으므로 넘어가지만 예시의 경우 비어있지 않기 때문에 pw의 뒤에서 꺼내와 wait의 앞으로 삽입한다.

 

이때 커서는 A 앞으로 이동한것과 마찬가지가 된다. (다음 입력이 pw의 제일 처음으로 삽입 될 것이기 때문!)

 

 A<B 

B 도 A 때와 동일하게 바로 pw 에 삽입한다.

이때는 커서가 B 옆으로 이동되고 위와 같은 상태가 된다. 

 

 A<B> 

> 가 입력 되면 A뒤로 커서가 이동하기 때문에 wait 덱 A를 꺼내와서 pw deque 뒤로 삽입한다.

위와 같이 커서가 이동한다.  

 

 A<B>c 

다음으로 c를 입력한다. 

 

 A<B>c- 

- 가 입력 되면 pw의 마지막 요소를 remove 한다. 

(코드에서 // *** 부분인데.. 나는 여기서 isEmpty 체크를 안해줘서 NoSuchElement 에러가 났다ㅠㅠ => 큐, 덱, 스택 등의 문제에서는 isEmpty 체크를 꼭 꼭 해야한다 !!)

ch 배열을 모두 순회했기 때문에 BA 가 최종 비밀번호가 된다.