길이가 N인 문자열 S = S0S1...SN-1이 주어졌을 때, 다음과 같은 쿼리를 수행해보자.
S = "abcdefgh"인 경우 쿼리 1 2 5는 아래와 같이 수행된다.
"abcdefgh" → "cdefabgh"
여기서 쿼리 2 4 6은 다음과 같이 수행된다.
"cdefabgh" → "cdefhabg"
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 100,000을 넘지 않는다.
둘째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ 100,000)가 주어진다. 셋째 줄부터 Q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.
3번 쿼리가 주어질 때마다 답을 출력한다. 3번 쿼리는 하나 이상 주어진다.
abcdefgh
5
3 5
1 2 5
3 5
2 4 6
3 5
f
b
a
이 문제는 사실 rope 자료구조나 slay tree를 이용해야 풀 수 있는 문제이다. Java로는 substring으로 풀어도 시간초과가 뜨지 않아 통과되었다.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );
StringBuilder str = new StringBuilder(br.readLine());
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
String[] input = br.readLine().split(" ");
if(input[0].equals("1")) {
String target = str.substring(Integer.parseInt(input[1]), Integer.parseInt(input[2])+1);
str.delete(Integer.parseInt(input[1]), Integer.parseInt(input[2])+1);
str.insert(0, target);
}
else if(input[0].equals("2")) {
String target = str.substring(Integer.parseInt(input[1]), Integer.parseInt(input[2])+1);
str.delete(Integer.parseInt(input[1]), Integer.parseInt(input[2])+1);
str.append(target);
}
else {
bw.write(str.charAt(Integer.parseInt(input[1]))+"\n");
}
}
bw.flush();
bw.close();
}
}