[ 백준 5397 키로거 ] 문제 풀이(Java) - 시뮬레이션 문제

 

시뮬레이션 문제를 풀어보았습니다.

 

어렵진 않지만 시간초과에 주의해야하는 문제입니다.

문제 설명 후 시간초과 났을 때 제가 주로 시도해보는 방법들도 같이 포스팅해보도록 하겠습니다.

 

 

문제보기

https://www.acmicpc.net/problem/5397

5397번: 키로거

 

나의 풀이

 

문제로 주어지는 문자열 안에 포함된 문자는 4가지 입니다.

 

1) '<' 문자 : 커서를 왼쪽으로 이동 (단, 이미 커서가 맨 왼쪽이면 이동하지 않는다)

2) '>' 문자 : 커서를 오른쪽으로 이동 (단, 이미 커서가 맨 오른쪽이면 이동하지 않는다)

3) '-' 문자 : 커서 바로 앞의 문자를 하나 지운다

4) 그 외의 알파벳 : 입력창에 알파벳 입력

 

그래서 제가 처음 생각했던 풀이는 수정이 가능한 StringBuilder 클래스에 비밀번호를 저장하고, 커서의 위치를 저장할 수 있는 변수를 하나 두어 커서의 위치에 따라 StringBuilder에 insert, delete 하는 방식으로 구현했습니다.

 

 

그런데,,,

시간초과가 났습니다 ㅠㅠ

 

아무래도 문자열이나 리스트의 중간에 계속해서 삽입, 삭제하는 경우에는 시간복잡도가 오래 걸립니다. 그 점을 간과했어요!

 

그래서 저는 StringBuilder 클래스 대신 스택을 이용하기로 했습니다.

 

스택을 2개 이용해서 커서 앞의 요소와 커서 뒤의 요소를 구분해주는 방식이죠

 

스택을 이용해 커서 기능 구현

 

다음과 같이 문자열이 "String"이고 커서가 t와 r 사이에 존재한다면 스택을 2개 이용하면 저렇게 나타낼 수 있습니다.

 

그럼 앞에서 말한 4개의 문자에 대한 기능을 다시 정의해보면,

 

1) '<' 문자 : 왼쪽 스택의 맨 위의 요소를 오른쪽 스택으로 옮긴다 (단, 왼쪽 스택이 비었다면 아무 일도 일어나지 않는다)

2) '>' 문자 : 오른쪽 스택의 맨 위의 요소를 왼쪽 스택으로 옮긴다 (단, 오른쪽 스택이 비었다면 아무 일도 일어나지 않는다)

3) '-' 문자 : 왼쪽 스택 맨 위의 요소를 하나 지운다 (단, 왼쪽 스택이 비었다면 아무 일도 일어나지 않는다)

4) 그 외의 알파벳 : 왼쪽 스택에 알파벳 하나 추가

 

구현하면 다음과 같습니다.

 

코드

//백준 5397번
//시뮬레이션 문제 풀이

package 백준;

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

public class N_5397 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int T = Integer.parseInt(br.readLine());
			for (int i = 0; i < T; i++) {
				String str = br.readLine();
				Stack<Character> front = new Stack<Character>();
				Stack<Character> back = new Stack<Character>();

				for (int j = 0; j < str.length(); j++) {
					if (str.charAt(j) == '<') {
						if (front.size() == 0)
							continue;
						back.push(front.pop());
					} else if (str.charAt(j) == '>') {
						if (back.size() == 0)
							continue;
						front.push(back.pop());
					} else if (str.charAt(j) == '-') {
						if(front.size() == 0)
							continue;
						front.pop();
					} else { // 알파벳
						front.push(str.charAt(j));
					}
				}
				
				
				while(!front.empty()) {
					back.push(front.pop());
				}
				StringBuilder pwd = new StringBuilder();
				while(!back.empty()) {
					pwd.append(back.pop());
				}
				
				System.out.println(pwd);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

시간초과 통과!

 

 

** 시간초과 시 시도해보면 좋은 방법들 **

 

1. Scanner 클래스 대신 BufferedReader 클래스 이용하기 + System.out 대신 BufferedWriter 이용하기 (bw.flush() 잊지말기!)

 

2. 문자열이나 리스트 중간에 삽입, 삭제 연산 -> 스택 2개 이용하는 것으로 바꿔보기

 

3. 완전탐색 시간 초과 -> 백트래킹 & 사다리 조작 같이 n개 이하의 사다리를 선택하는 것이면 사다리 0개, 사다리 1개, 사다리 2개, 사다리 3개 처럼 갯수를 나누고 이전 단계에서 구해지면 바로 리턴

 

4. 정수 자리수 조작해서 다른 숫자 만드는 연산은 큐보다는 /와 % 연산을 이용해서 조작하는 것이 훨씬 빠름

 

5. 순열보단 조합이 빠르다.

 

6. 문자열 append 할 때 '+' 연산을 이용하는 것보다는 StringBuilder의 .append()를 이용해라!

 

7. 출력해야할 값이 너무 많은 경우 -> System.out 이용하기보다는 StringBuilder에 출력해야할 값 모두 저장해두고 한 번만 System.out 이용!