[백준 5397번][Java] 키로거 - 덱

www.acmicpc.net/problem/5397

5397번: 키로거

 

핵심은 <, >같은 쉬프트 연산을 어떻게 구현할 것인가에 달려 있습니다. 단순 리스트로 구현해서 인덱스를 추적해가면서 문자열을 조작해 구현할 수도 있겠으나 덱 구조를 이용하면 쉽게 구현이 가능합니다. 

 

 

풀이

 

임의의 문자열 S가 있다고 합시다. 문자열을 추가할 때, 커서가 추가된 문자의 뒤에 생성된다고 가정합니다. 초기의 문자열 S는 다른 연산없이 문자를 추가만 한 상태입니다. 각 과정은 S에 대해 차례로 왼쪽, 오른쪽으로 커서를 이동하는 과정을 나타냅니다.

 

핵심은 커서를 기준으로 공간을 나누는겁니다. 커서 왼쪽은 password라고 하고 커서 왼쪽은 임시 저장공간 temp라고 지정했습니다.  커서를 왼쪽으로 이동하면 password의 마지막 요소를 pop해 temp의 앞에 넣어줍니다. 그리고 커서를 오른쪽으로 다시 이동시키면 temp의 요소를 앞에서 pop해 password의 뒤에 넣어줍니다. 삭제 연산의 경우는 간단한데 password의 마지막 요소를 pop해줍니다. 이렇게 구현할 경우의 장점은 일일이 커서의 위치를 추적할 필요가 없습니다.

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/*
키로거
https://www.acmicpc.net/problem/5397
 */
public class Main {
	static int n;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		n = reader.readInt();
		for (int i = 0; i < n; i++) {
			String keyLog = reader.readLine().trim();
			System.out.println(getPassword(keyLog));
		}
	}

	private static String getPassword(String keyLog) {
		ArrayDeque<Character> password = new ArrayDeque<>();
		ArrayDeque<Character> temp = new ArrayDeque<>();

		for (int i = 0; i < keyLog.length(); i++) {
			char log = keyLog.charAt(i);

			switch (log) {
				case '<' : {
					if(!password.isEmpty()) {
						temp.addFirst(password.pollLast());
					}
					break;
				}
				case '>': {
					if(!temp.isEmpty()) {
						password.addLast(temp.pollFirst());
					}
					break;
				}
				case '-' : {
					if(!password.isEmpty()) {
						password.pollLast();
					}
					break;
				}
				default:{
					password.addLast(log);
				}
			}
		}
		StringBuilder sb = new StringBuilder();

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

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

		return sb.toString();
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}