백준 : 1360 되돌리기

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

1360번: 되돌리기

 

처음에는 구현이 까다로워 보인다. undo에 undo에 undo를 어떻게 계산해야할지가 햇갈린다.

 

하지만 제일 마지막에 실행하는 undo를 기준으로 생각해본다면 명령어를 실행하지 않을 것들을 채택할수 있다.

 

마지막 undo부터 차례대로 그범위안의 명령어들을 비활성화 시켜나가면 최종적으로는 undo를 제외한 type만 남는다.

 

그리고 이것이 정답이 된다.

 

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

public class 되돌리기 {
	static int N;

	static class TYPE {
		String name;
		char alpa;
		int curTime;
		int backTime;

		public TYPE() {
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		TYPE type[] = new TYPE[N];
		boolean check[] = new boolean[N];

		// INPUT
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			type[i] = new TYPE();
			if (st.nextToken().equals("type")) {
				type[i].name = "type";
				type[i].alpa = st.nextToken().charAt(0);
				type[i].curTime = Integer.parseInt(st.nextToken());
			} else {
				type[i].name = "undo";
				type[i].backTime = Integer.parseInt(st.nextToken());
				type[i].curTime = Integer.parseInt(st.nextToken());
			}
		}

		// undo를 없애보자
		for (int i = N - 1; i >= 0; i--) {
			// 죽은 명령어는 볼필요가 없다.
			if (check[i])
				continue;

			if (!type[i].name.equals("undo")) {
				continue;
			}

			check[i] = true;

			// curtime - backtime 안에 들어오는 시간을 조사한다.
			int look = type[i].curTime - type[i].backTime;

			for (int j = i - 1; j >= 0; j--) {
				if (look > type[j].curTime)
					break;
				check[j] = true;
			}
		}

		// undo 를 없애고나면 type만 남을꺼다. 이제 StringBuilder로 추가해보자
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			if (check[i])
				continue;
			sb.append(type[i].alpa);
		}
		System.out.println(sb.toString());
	}
}