[HackerRank] Simple Text Editor

Problem

---

Implement a simple text editor. The editor initially contains an empty string, S. Perform Q operations of the following 4 types:

1. append(W) - Append string W to the end of S.
2. delete(k) - Delete the last k characters of S.
3. print(k) - Print the k^th character of S.
4. undo - Undo the last (not previously undone) operation of type 1 or 2, reverting S to the state it was in prior to that operation.

Example

S = 'abcde'

ops = ['1 fg', '3 6', '2 5', '4', '3 7', '4', '3 4']

operation
index   S       ops[index]  explanation
-----   ------  ----------  -----------
0       abcde   1 fg        append fg
1       abcdefg 3 6         print the 6th letter - f
2       abcdefg 2 5         delete the last 5 letters
3       ab      4           undo the last operation, index 2
4       abcdefg 3 7         print the 7th characgter - g
5       abcdefg 4           undo the last operation, index 0
6       abcde   3 4         print the 4th character - d

The results should be printed as:

f
g
d

Input Format

The first line contains an integer, Q, denoting the number of operations.
Each line i of the Q subsequent lines (where 0 ≤ i ≤  Q) defines an operation to be performed. Each operation starts with a single integer, t (where t ∈ {1, 2, 3, 4}), denoting a type of operation as defined in the Problem Statement above. If the operation requires an argument, t is followed by its space-separated argument. For example, if t = 1 and W = "abcd", line i will be 1 abcd.

Constraints

• 1 ≤ Q ≤ 10^6
• 1 ≤ k ≤ |S|
• The sum of the lengths of all W in the input ≤  10^6.
• The sum of k over all delete operations ≤  2*10^6.
• All input characters are lowercase English letters.
• It is guaranteed that the sequence of operations given as input is possible to perform.

Output Format

Each operation of type 3 must print the k^th character on a new line.

Sample Input

STDIN   Function
-----   --------
8       Q = 8
1 abc   ops[0] = '1 abc'
3 3     ops[1] = '3 3'
2 3     ...
1 xy
3 2
4 
4 
3 1

Sample Output

c
y
a

Explanation

Initially, S is empty. The following sequence of 8 operations are described below:

1. S = "". We append abc to S, so S = "abc".
2. Print the 3rd character on a new line. Currently, the 3rd character is c.
3. Delete the last 3 characters in S (abc), so S = "".
4. Append xy to S, so S = "xy".
5. Print the 2nd character on a new line. Currently, the 2nd character is y.
6. Undo the last update to S, making S empty again (i.e., S = "").
7. Undo the next to last update to S (the deletion of the last 3 characters), making S = "abc".
8. Print the 1st character on a new line. Currently, the 1st character is a.

---

간단한 텍스트 편집기를 구현하세요. 이 편집기에는 처음에 빈 문자열 S가 들어 있습니다. 다음의 4가지 유형의 연산 중 Q개의 연산을 수행하세요.

1. append(W) - 문자열 W를 S의 끝에 추가합니다.
2. delete(k) - S의 마지막 k 문자를 삭제합니다.
3. print(k) - S의 k번째 문자를 출력합니다.
4. undo - 마지막으로 수행된 1번 또는 2번 유형의 연산을 취소하여 S를 그 연산 이전 상태로 되돌립니다.

예제

S = 'abcde'
ops = ['1 fg', '3 6', '2 5', '4', '3 7', '4', '3 4']

연산 인덱스	S	ops[연산 인덱스]	설명
0	abcde	1 fg	문자열 fg 추가
1	abcdefg	3 6	6번째 문자 출력 (f)
2	abcdefg	2 5	마지막 5 문자 삭제 (S = ab)
3	ab	4	마지막 연산(삭제) 취소 (S = abcdefg로 복구)
4	abcdefg	3 7	7번째 문자 출력 (g)
5	abcdefg	4	마지막 연산(문자열 추가) 취소 (S = abcde로 복구)
6	abcde	3 4	4번째 문자 출력 (d)

 

입력 형식

첫 번째 줄에는 연산의 수를 나타내는 정수 Q가 주어집니다.
다음 Q개의 줄에는 각각의 연산을 나타내는 문자열이 주어집니다. 각 연산은 t로 시작하며, 필요한 경우 인수가 뒤에 붙습니다. 예를 들어 t = 1이고 W = "abcd"인 경우 1 abcd로 주어집니다.

 

제약 조건

• 1 ≤ Q ≤ 10^6
• 1 ≤ k ≤ |S|
• 모든 W의 총 길이 합은 10^6을 넘지 않습니다.
• 모든 삭제 연산의 k의 합은 2×10^6을 넘지 않습니다.
• 모든 입력 문자는 영어 소문자입니다.
• 주어진 연산 순서가 실행 가능한 순서로 주어집니다.

출력 형식

타입 3의 연산이 실행될 때마다 k번째 문자를 새 줄에 출력해야 합니다.

 

728x90

 

 

 

Solution

---

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

public class Solution {
    public static void main(String[] args) {
        // 입력을 읽고, 출력할 때 성능을 위해 BufferedReader와 StringBuilder 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder output = new StringBuilder();
        
        try {
            int Q = Integer.parseInt(br.readLine());
            StringBuilder S = new StringBuilder();
            Stack<String> history = new Stack<>();

            for (int i = 0; i < Q; i++) {
                String[] operation = br.readLine().split(" ");
                int opType = Integer.parseInt(operation[0]);

                if (opType == 1) {
                    // append(W)
                    history.push(S.toString());
                    String W = operation[1];
                    S.append(W);

                } else if (opType == 2) {
                    // delete(k)
                    history.push(S.toString());
                    int k = Integer.parseInt(operation[1]);
                    S.delete(S.length() - k, S.length());

                } else if (opType == 3) {
                    // print(k)
                    int k = Integer.parseInt(operation[1]);
                    output.append(S.charAt(k - 1)).append("\n");

                } else if (opType == 4) {
                    // undo
                    S = new StringBuilder(history.pop());
                }
            }

            // 결과 출력
            System.out.print(output.toString());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

 

 

• BufferedReader와 StringBuilder를 사용하여 효율적으로 입력을 읽고 출력을 관리합니다.
• history 스택을 사용하여 append와 delete 연산을 수행하기 전의 상태를 저장해 undo 시 쉽게 복구할 수 있습니다.
• S는 StringBuilder로 관리하여 문자열을 효율적으로 조작하며, 연산의 결과는 최종적으로 output에 저장해 한 번에 출력합니다.

---

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder output = new StringBuilder();

 

• 기능: BufferedReader와 StringBuilder 객체를 생성합니다.
• 사용 이유: BufferedReader는 콘솔로부터 효율적으로 입력을 읽어오는 데 사용되며, StringBuilder는 여러 줄의 출력을 하나로 모아 빠르게 출력하기 위해 사용됩니다.

int Q = Integer.parseInt(br.readLine());

 

 

• 기능: Q는 수행할 명령어의 개수를 나타내는 정수입니다.
• 사용 이유: 반복문에서 Q만큼 명령을 수행하기 위해 명령 수를 저장합니다.

StringBuilder S = new StringBuilder();
Stack<String> history = new Stack<>();

 

• 기능: S는 현재 문자열을 나타내고, history는 undo 기능을 위한 스택입니다.
• 사용 이유: S는 문자열의 현재 상태를 저장하며, history 스택은 문자열의 이전 상태를 저장하여 undo 명령 시 이전 상태로 돌아갈 수 있도록 합니다.

String[] operation = br.readLine().split(" ");
int opType = Integer.parseInt(operation[0]);

 

 

• 기능: 현재 명령어를 읽어 공백 기준으로 분리하고, 명령어의 타입을 확인합니다.
• 사용 이유: 명령어의 종류(opType)를 구분해 각 기능을 수행할 수 있도록 합니다.

append(W) 연산

if (opType == 1) {
    history.push(S.toString());
    String W = operation[1];
    S.append(W);
}

 

• 기능: 문자열 W를 S의 끝에 추가합니다.
• 사용 이유: 새 문자열을 추가하기 전 history에 현재 문자열 상태를 저장하여 undo 시 이전 상태로 돌아갈 수 있게 합니다.

delete(k) 연산

else if (opType == 2) {
    history.push(S.toString());
    int k = Integer.parseInt(operation[1]);
    S.delete(S.length() - k, S.length());
}

 

 

• 기능: S의 마지막 k개의 문자를 삭제합니다.
• 사용 이유: 삭제 전 상태를 history에 저장하여 undo 시 복원할 수 있도록 합니다

 

print(k) 연산

else if (opType == 3) {
    int k = Integer.parseInt(operation[1]);
    output.append(S.charAt(k - 1)).append("\n");
}

 

 

• 기능: 문자열 S에서 k번째 문자를 output에 추가합니다.
• 사용 이유: 지정된 위치의 문자만을 출력하기 위해 사용하며, output을 모아 한 번에 출력하는 방식을 취합니다.

undo 연산

else if (opType == 4) {
    S = new StringBuilder(history.pop());
}

 

 

• 기능: 마지막 append 또는 delete 연산을 되돌립니다.
• 사용 이유: 이전 상태를 history 스택에서 꺼내어 S에 복원하여 undo 기능을 구현합니다.

} catch (IOException e) {
    e.printStackTrace();
}

 

 

• 기능: 입출력 예외가 발생할 경우 예외 메시지를 출력합니다.
• 사용 이유: BufferedReader 사용 시 발생할 수 있는 예외를 처리하여 프로그램이 비정상 종료되지 않도록 합니다.