백준 1360 되돌리기 자바(java)

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

1360번: 되돌리기

 

풀이 방법

undo 를 어떻게 구현할 것인가가 핵심이다.

처음에 접근한 방식은 undo 가 나올때 마다 직접 지워주거나 추가해주면서 주어진 시간만큼 되돌아 가는 것을 직관적으로 구현하려고 했으나 undo 가 연속될 수록 구현이 까다롭다고 느꼈다..(나만 그럴수도..)

 

따라서 조금 더 쉬운 방식은 그때그때 명령을 수행할 때마다 수행한 시간과 그 때의 문자열 상태를 저장해주는 것이다. 명령 수행시간과 상태가 저장되어 있으므로 undo 수행 시 되돌려야 하는 최소 시간만 구하면 그 시간보다 빨리 수행된 마지막 명령의 상태로 돌아가기만 하면 된다.

undo 3 5 에서 되돌려야 하는 최소 시간은 5-3=2초이므로 2초보다 수행된 시간이 빠른 명령을 찾으면 된다.

 

주의할 점은 되돌아갈 곳이 없는 경우도 있다는 것이다. 

처음부터 undo 1 1 이 나오면 1-1=0 이므로 0보다 수행 시간이 빠른 상태는 찾을 수 없다.

따라서 이런 경우엔 빈 문자열을 삽입하여 처리해주어야 한다.

 

코드

import java.io.*;

public class Main {

    static class TimeStamp {
        String status; // 문자열 상태
        int time; // 수행된 시간
        public TimeStamp(String status, int time) {
            this.status = status;
            this.time = time;
        }
    }

    static TimeStamp[] timeStamps;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        timeStamps = new TimeStamp[N+1];
        timeStamps[0] = new TimeStamp("", 0); // 0초 빈 문자열 세팅
        for(int i=1; i<N+1; i++) {
            String[] command = br.readLine().split(" ");

            if(command[0].equals("type")) { // type 명령이면
                // 직전 수행된 명령의 문자열 상태에 문자를 붙여 삽입
                timeStamps[i] = new TimeStamp(timeStamps[i-1].status + command[1], Integer.parseInt(command[2]));

            } else { // undo 명령이면
                // 수행 시간에서 되돌릴 시간 t 를 빼서 되돌려야 하는 최소 수행 시간을 찾음
                int range = Integer.parseInt(command[2]) - Integer.parseInt(command[1]);
                undo(i, range, Integer.parseInt(command[2])); // 되돌리기 수행
            }
        }

        System.out.println(timeStamps[N].status);
    }

    // 되돌리기 수행
    public static void undo(int i, int range, int time) {
        boolean back = false; // 되돌릴 상태가 있는 지 여부
        // 되돌아 갈 timestamp 상태를 찾음
        for(int j=i-1; j>=0; j--) {
            // 되돌려야 최소 수행 시간보다 수행된 시간이 작아지는 timestamp 가 되돌아 갈 곳
            if(timeStamps[j].time < range) {
                timeStamps[i] = new TimeStamp(timeStamps[j].status, time);
                back = true;
                break;
            }
        }
        // 되돌아 갈 곳이 없다면 빈 문자열 삽입
        if(!back) {
            timeStamps[i] = new TimeStamp("", time);
        }
    }
}