[BOJ]백준5397번: 키로거(JAVA)
https://www.acmicpc.net/problem/5397
문제
창영이는 컴퓨터에 키 입력을 하면 입력한 키를 바탕으로 비밀번호를 알아 내고 싶어한다.
- 길이가 L인 문자열의 길이는 최대 1,000,000이다.
- ← 를 입력하면 현재 문자열 커서에서 한 칸 왼쪽으로 가서 문자를 입력한다.
- → 를 입력하면 현재 문자열 커서에서 한 칸 오른쪽으로 가서 문자를 입력한다.
풀이
- 문자열의 크기가 1,000,000 이므로 배열로 해결하기가 어렵다.
- 스택을 활용하여, 선형시간 문제를 해결할 수 있는 알고리즘을 설계한다.
- 스택 두 개를 만들고, 스택 두 개의 중간 지점을 커너로 간주한다.
- 문자입력: 왼쪽 스택에 원소를 삽입한다.
- BackSpace 입력 : 왼쪽 스택에서 문자를 삭제한다.
- ← 입력 : 왼쪽 스택에서 오른쪽 스택으로 원소를 이동한다.
- → 입력 : 오른쪽 스택에서 왼쪽 스택으로 원소를 이동한다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
class Baekjoon_5397 {
public static void main(String[] args) throws IOException {
// BufferedREader 를 통해 입력 값 얻기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
String[] input;
// Test케이스의 갯수를 입력받는 코드
// String 배열의 input 생성
for(int i=0;i<T;i++) {
Stack<String> left = new Stack<>();
Stack<String> right = new Stack<>();
input = br.readLine().split("");
for (String str : input) {
switch (str) {
case "<":
if(!left.isEmpty()){
right.push(left.pop());
}
break;
case ">":
if (!right.isEmpty()) {
left.push(right.pop());
}
break;
case "-":
if (!left.isEmpty()) {
left.pop();
}
break;
default:
left.push(str);
}
}
while (!left.isEmpty()) {
right.push(left.pop());
}
while (!right.isEmpty()) {
sb.append(right.pop());
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
Author And Source
이 문제에 관하여([BOJ]백준5397번: 키로거(JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hoha/BOJ백준5397번-키로거JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)