[JAVA] 백준 1360 되돌리기

 

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

 

 

문제분석

코테 감 되찾기위한 문제..

시간복잡도가 계속 신경쓰여서 AI 한테 물어보니, TreeMap이라는 자료형을 알려줬다. 근데 성능이 기가막히긴한데...이정도까지 알아야 할까? 근데 확실히 이런걸 다 알면 코테에서 매우 유리해질 것 같아서 다 알고 가야할 듯 하긴 하다.

 

문제는 어렵지 않다. undo를 처리하기 위해 기록을 잘 저장하며 진행해나가면 된다. 하지만 undo할 시간대에 진행한 작업이 없었을 때 처리하는게 약간 어려웠는데, TreeMap 도입해서 한방에 해결했다.

 

 

코드

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


public class Main{

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int prevTime = 0; // 이전 명령어 시간
        // a, ab, " ", a
        TreeMap<Integer, String> result = new TreeMap<>(); // 시간: 완성된 문자
        result.put(prevTime,"");
        for(int i = 0; i < N; i++){
            String input = br.readLine();
            String[] inputArr = input.split(" ");
            String cmd = inputArr[0];
            String cmd2 = inputArr[1];
            int time = Integer.parseInt(inputArr[2]);
            if(cmd.equals("type")){
                result.put(time,result.get(prevTime)+cmd2);
            }else if(cmd.equals("undo")){
                int undoTime = Integer.parseInt(cmd2);
                if(undoTime >= time - 1){// 처음으로 돌아가기
                    result.put(time, "");
                }else{
                    int key = result.floorKey(time - undoTime - 1);// time - undoTime 보다 작은 값중에 가장 큰 값 - 우리가 되돌리려는 값이기 때문에 1 빼야 함.
                    result.put(time, result.get(key));
                }
            }
            prevTime = time;
        }
        System.out.println(result.get(prevTime));

    }
}