백준 - 1360 되돌리기(Java)

www.acmicpc.net/problem/1360

1360번: 되돌리기

 

1. 유형

구현

 

2. 풀이

이 문제의 핵심은 중첩된 undo의 해결법이다.

undo, undo, undo 이렇게 3개만 겹쳐도 어려워진다. 

 

처음 풀떄는, undo가 나올때마다 주어진 시간만큼 되돌아가는 식으로 풀려고 했지만 난이도가 너무 노가다이고 어려웠다. 따라서 다시 생각했다.

 

풀이법은 각 상태를 시간초 마다 저장하는 것이다. 

 

 

4
type a 1
type b 2
type c 3
undo 3 5

0	1	2	3	4
{"", 0}	{"a", 1}	{"ab", 2}	{"abc", 3}	{"a",5}

이런식으로 각 상태를 저장 후, undo가 나왔을때 해당 노드로 돌아가는 것이다. 3초 뒤로 돌아가는 것이면, 

index를 4-1부터 시작해서 0까지 탐색을 하면 노드의 시간이 5-3-1보다 작아지는 곳을 찾으면 된다. 그후, 그 노드를 불러오면 끝.

 

3. 디버깅 실수

런타임에러 - 만약 처음 부터 undo 3 3이 나오는 경우가 있다. 이러면 index 오류가 나온다. 그래서 flag값으로 예외 처리를 해줘야한다.

 

출력 형식 에러 - 맨 처음 0초때 노드를 넣을때, " " 처럼, 공백문자가 아닌 띄어쓰기를 넣었더니 출력형식 에러가 나왔다.

그냥 "" 처럼, 띄어쓰기를 없애줘야한다.

 

실제 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N;
	static ArrayList<Node> list;
	static class Node{
		String str;
		int time;
		public Node(String str, int time) {
			this.str = str;
			this.time = time;
		}
	}
	static void input() throws IOException {
		st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		list = new ArrayList<>();
		list.add(new Node("", 0));
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(in.readLine());
			String str = st.nextToken();
			if("type".equals(str)) {
				Node pre = list.get(i-1);
				char c = st.nextToken().charAt(0);
				int n = Integer.valueOf(st.nextToken());
				list.add(new Node(pre.str+c, n));
			}else {
				int start = Integer.valueOf(st.nextToken());
				int end = Integer.valueOf(st.nextToken());
				undo(i, end - start -1, end);
			}
		}
		
	}
	
	static void undo(int cur_idx ,int target_time, int cur_time) {
		boolean flag = false;
		for(int i=cur_idx-1; i>=0; i--) {
			if(target_time <0)
				break;
			Node cur = list.get(i);
			if(cur.time <= target_time) {
				list.add(new Node(cur.str, cur_time));
				flag = true;
				break;
			}
		}
		if(!flag) {
			list.add(new Node("", cur_time));
		}
	}
	
	public static void main(String[] args) throws IOException {
		input();
		System.out.print(list.get(N).str);
	}
}