키로거 (5397번)
https://www.acmicpc.net/problem/5397
풀이방법
- 스택을 구현한다.
- 처음에는 자바 내장 클래스를 이용했지만 속도가 느려서 배열로 직접 간단히 구현했다.
- 1000ms -> 740ms로 줄어들었다.
- 입력 데이터를 하나씩 분석한다.
<문자일 경우 스택에서pop한 후 임시 스택에 보관한다.>문자일 경우 임시 스택에서pop한 후 스택에 보관한다.-문자일 경우 스택에서 제거한다.- 역순으로 저장되므로 반환할 때
revese메소드를 이용해 역으로 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static class Stack {
int pos = 0;
int countOfData = 0;
char[] array = null;
public Stack(int size) {
array = new char[size];
}
public char pop() {
countOfData--;
char rData = array[--pos];
array[pos] = 0;
return rData;
}
public void push(char c) {
array[pos++] = c;
countOfData++;
}
public boolean isEmpty() {
return (countOfData == 0);
}
public int size() {
return countOfData;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
char[] input = null;
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
input = br.readLine().toCharArray();
sb.append(keylog(input)).append('\n');
}
System.out.println(sb);
}
private static String keylog(char[] input) {
Stack keylogger = new Stack(input.length);
Stack tmpInputs = new Stack(input.length);
for(int i=0; i<input.length; i++) {
switch (input[i]) {
case '<':
if (keylogger.size() == 0) break;
tmpInputs.push(keylogger.pop()); break;
case '>':
if (tmpInputs.isEmpty()) break;
keylogger.push(tmpInputs.pop()); break;
case '-':
if (keylogger.isEmpty()) break;
keylogger.pop();
break;
default:
keylogger.push(input[i]);
break;
}
}
StringBuilder sb = new StringBuilder();
while (!tmpInputs.isEmpty()) keylogger.push(tmpInputs.pop());
while (!keylogger.isEmpty()) sb.append(keylogger.pop());
return sb.reverse().toString();
}
}
Comments powered by Disqus.