[백준] 1360번 되돌리기 자바 풀이

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

128 MB

1515

457

365

33.610%

문제

민식이는 다음과 같이 두 개의 명령만 지원하는 새로운 텍스트 에디터를 만들었다.

• “type c" : 현재 글의 가장 뒤에 문자 c를 추가한다.
• “undo t" : 이전 t초동안 수행된 작업을 역순으로 되돌린다.

처음 텍스트 에디터는 비어있다.

예를 들어, 다음과 같은 명령을 진행했다고 하자.

• 1초 : type a
• 2초 : type b
• 3초 : type c
• 5초 : undo 3

3초가 끝날 때, 텍스트는 "abc"이다. 5초때, 이전 3초동안 한 작업을 역순으로 되돌려야 한다. c는 지워지고, b도 지워질 것이다. 따라서 a만 남는다.

되돌리기가 되돌리기 될 수도 있다.

예를 들어

• 1초 : type a
• 2초 : type b
• 3초 : undo 2
• 4초 : undo 2

2초일 때, 텍스트는 “ab"이다. 3초때 모든 것이 되돌리기 되므로 텍스트는 빈 텍스트가 되고, 4초때 3초때 되돌리기 한 것이 되돌리기 되고, 2초때 type b한 것이 지워진다. 따라서 텍스트는 ”a"가 된다.

명령과 수행한 시간이 주어질 때, 마지막에 남은 텍스트를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 명령의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 명령과 수행한 시간이 주어진다. 항상 시간이 오름차순으로 주어지고, type c에서 c는 알파벳 소문자, undo t에서 t는 1보다 크거나 같고 109보다 작거나 같은 자연수이다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 명령을 수행한 후에 남아있는 텍스트를 출력한다.

풀이

아이디어를 떠올리는것이 굉장히 어려워 해답을 봤음.

처음엔 스택을 통해 undo 시 해당 로그를 저장하고 복구하는 형식으로 구현하려고 했는데, undo가 중첩되었을 때 구현을 어떻게 해야할지 잘 떠오르지 않았다.

그러나 해답을 보던 중 아래의 방법을 사용하여 다시 풀어봤다.

각 명령이 들어올때마다 벡터에 해당 시간과 문자를 저장하고 undo 명령시 (현재 시간 - t)초 이전의 상태를 불러오면 됩니다.

type 명령의 경우, 리스트의 가장 끝에 있는 데이터에 추가로 문자를 더해준 후 리스트에 추가한다.

undo 명령의 경우 리스트의 끝부터 순회하며, 리스트의 아이템의 시간보다 입력된 시간 - undo 시간이 크다면 해당 문자열을 리스트에 추가한다.(undo가 적용된 문자열을 리턴)

되돌리기라는 이름을 듣고 바로 스택을 써야한다고만 생각했는데, 문제를 보는 시각을 더 늘리자..

코드

package com.company.baekjoon;

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

public class B1360 {

    static ArrayList<Pair> list = new ArrayList<>();

    public static class Pair {
        int first;
        String second;
        public Pair(int first, String second) {
            this.first = first;
            this.second = second;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        list.add(new Pair(0, ""));
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            String prompt = st.nextToken();

            if (prompt.equals("type")) {
                String character = st.nextToken();
                int time = Integer.parseInt(st.nextToken());
                list.add(new Pair(time, list.get(list.size()-1).second + character));
            } else {
                int undo = Integer.parseInt(st.nextToken());
                int time = Integer.parseInt(st.nextToken());
                list.add(new Pair(time, getStr(time-undo)));
            }
        }
        System.out.println(list.get(list.size()-1).second);

    }
    public static String getStr(int second) {
        for (int i = list.size()-1; i >= 0; i--) {
            if (list.get(i).first < second) {
                return list.get(i).second;
            }
        }
        return "";
    }
}