아이디어

• Doubly linked list와 배열(hist ← history), 두 자료구조로 상태를 관리하자.
  • 현재 가리키고 있는 노드를 head라 하자.
  • 최초의 head는 -1 값을 가지고 있는 더미 노드다.
  • hist[i]에는 i번째 변경 전의 head를 가리킨다.
• '추가' 쿼리라면 새로운 노드를 만들어 head와 연결시키고, head가 그 노드를 가리키게 한다. 이때 분기가 일어난다.
• '삭제' 쿼리라면 head의 이전 노드로 돌아간다.
  • 주의: 다시 이 쿼리의 전으로 돌아올 수 있으므로 실제로 노드를 삭제하면 안 된다.
• '시간 이동' 쿼리라면 K번째 이전 노드, 즉 hist[K]로 head를 되돌린다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, K;
	static char c;
	static Node[] hist;
	static Node head;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		hist = new Node[N+1];
		head = new Node(-1, null);
		
		for (int i=1; i<=N; i++) {
			tk = new StringTokenizer(rd.readLine());
			c = tk.nextToken().charAt(0);
			if (tk.hasMoreTokens())
				K = Integer.parseInt(tk.nextToken());
			
			hist[i] = head;
			switch (c) {
			case 'a':
				head = new Node(K, head);
				break;
			case 's':
				head = head.prev;
				break;
			case 't':
				head = hist[K];
				break;
			}
			sb.append(head.n).append('\n');
		}
		
		System.out.println(sb);
	}
	
	static class Node {
		int n;
		Node prev, next;
		
		Node(int n, Node prev) {
			this.n = n;
			this.prev = prev;
			if (prev != null)
				prev.next = this;
		}
	}
}

메모리 및 시간

• 메모리: 36772 KB
• 시간: 424 ms

리뷰

• 알고리즘 분류를 먼저 봤다면 '스택'이라는 점에 의존해 함정에 빠졌을 것 같다.
• (23.11.03 수정) 굳이 이중 리스트일 필요도 없었다! next는 쓰지도 않았다.