문제
키 입력 로그가 주어질 때 최종 비밀번호를 구하라. <와 >는 커서 이동, -는 삭제이다.
입력
테스트 케이스 수 T, 각 케이스에 키 입력 문자열이 주어진다.
출력
각 케이스마다 비밀번호를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 <<BP<A>>Cd- ThIsIsS3662 | ABPC ThIsIsS3662 |
풀이
LinkedList의 ListIterator로 커서 위치를 관리하며 삽입/삭제/이동을 처리한다.
- ListIterator를 커서로 사용한다
<이면previous(),>이면next()로 커서를 이동한다-이면previous()후remove()로 삭제한다- 일반 문자는
add()로 커서 위치에 삽입한다
핵심 아이디어: LinkedList의 ListIterator는 커서 위치에서의 삽입/삭제를 O(1)에 처리하므로, 전체 O(N)에 해결된다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day554BOJ5397키로거 {
public static void main(String[] args) throws Exception {
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++) {
LinkedList<Character> list = new LinkedList<>();
ListIterator<Character> iter = list.listIterator();
String str = br.readLine();
for (int j = 0; j < str.length(); j++) {
char command = str.charAt(j);
switch (command) {
case '<':
if (iter.hasPrevious()) {
iter.previous();
}
break;
case '>':
if (iter.hasNext()) {
iter.next();
}
break;
case '-':
if (iter.hasPrevious()) {
iter.previous();
iter.remove();
}
break;
default:
iter.add(command);
}
}
for (char c : list) {
bw.write(c);
}
bw.newLine();
}
br.close();
bw.close();
}
}복잡도
- 시간: O(T * L) - L은 문자열 길이
- 공간: O(L)