
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));
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1025 제곱수 찾기 (0) | 2026.02.14 |
|---|---|
| [JAVA] 백준 1022 소용돌이 예쁘게 출력하기 (0) | 2026.02.13 |
| [JAVA] 백준 1043 거짓말 (0) | 2025.10.04 |
| [JAVA] 백준 2413 비슷한 순열 (0) | 2025.09.22 |
| [JAVA] 백준 1135 뉴스 전하기 (0) | 2025.09.09 |