https://www.acmicpc.net/problem/1406
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
List<Character> list = new ArrayList<>();
for(int i=0; i<s.length(); i++){
list.add(s.charAt(i));
}
int tc = Integer.parseInt(br.readLine());
int idx=list.size();
while(tc-- != 0 ){
StringTokenizer st = new StringTokenizer(br.readLine());
String command = st.nextToken();
if(command.equals("L")){
if(idx!=0)idx--;
}else if(command.equals("D")){
if(idx !=list.size())idx++;
}else if(command.equals("B")){
if(idx!=0){
idx--;
list.remove(idx);
}
}else if(command.equals("P")){
char word = st.nextToken().charAt(0);
list.add(idx, word);
idx++;
}
}
String answer="";
for(char c : list){
answer += Character.toString(c);
}
System.out.println(answer);
}
}
ArrayList를 사용한 풀이이다.
여기서 문제가 발생하게 되는데 ArrayList는 삽입과 삭제가 일어날 때 O(N)번의 연산을 수행하게 된다.
해당 문제에서는 삽입과 삭제 자료구조를 돌아다니는 조회가 빈번하게 일어난다. 이를 빠르게 해결할 방법을 찾아야한다.
에전에 c++로 문제를 풀었을 떄 사용한 방법이다. iter를 구현해서 iter이 가르키는 값을 이용해 값을 가공?하는 방법이다.
package math.순열;
import java.io.*;
import java.util.*;
public class Practice {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = br.readLine();
LinkedList<Character> list = new LinkedList<Character>();
for(int i=0; i<s.length(); i++){
list.add(s.charAt(i));
}
int tc = Integer.parseInt(br.readLine());
ListIterator<Character> iter = list.listIterator();
while(iter.hasNext()){// iterator를 이용해서 마지막 커서 위치로 이동시킨다.
iter.next();
}
while(tc-- != 0 ){
StringTokenizer st = new StringTokenizer(br.readLine());
String command = st.nextToken();
if(command.equals("L")){
if(iter.hasPrevious()) iter.previous(); //왼쪽으로 이동
}else if(command.equals("D")){
if(iter.hasNext()) iter.next();//오른쪽으로 이동
}else if(command.equals("B")){
if(iter.hasPrevious()){
iter.previous(); //왼쪽으로 이동
iter.remove(); //remove는 previous나 next로 반환된 가장 마지막 요소를 제거한다.
//즉 remove하기 전에 iter을 움직여줘고 바로 삭제해야 원하는 값을 지운다는 뜻
}
}else if(command.equals("P")){
char word = st.nextToken().charAt(0);
iter.add(word);
}
}
for(char c : list){
bw.write(Character.toString(c)) ;
}
bw.flush();;
bw.close();
}
}
애초에 List가 아니라 Stack을 이용해서도 가능하다.
Stack은 삽입, 삭제가 O(1)으로 이루어진다. 왼쪽 오른쪽을 나눠서 Stack에 저장하면 된다.
커서의 위치가 좌우로 1회만 이동한다고 가정했을 때 사용할 수 있는 방안이다.
커서의 왼쪽에 값을 넣어주고 오른쪽 Stack에 값을 거꾸로 넣어주면 된다.
그리고 커서를 왼쪽 이동할 때 왼쪽의 stack에서 값을 뺀 후 오른쪽 Stack에 push해주면 된다!!
import java.io.*;
import java.util.*;
public class Practice {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s = br.readLine();
int tc = Integer.parseInt(br.readLine());
Stack<Character> left = new Stack<>();
Stack<Character> right = new Stack<>();
//값 세팅하기
for(int i=0 ;i< s.length(); i++){
left.push(s.charAt(i));
}
while(tc-- != 0 ){
StringTokenizer st = new StringTokenizer(br.readLine());
String command = st.nextToken();
if(command.equals("L")){
//왼쪽으로 이동
// 왼쪽에서 빼서 오른쪽으로 넣어주기
if(!left.isEmpty()){
right.push(left.pop());
}
}else if(command.equals("D")){
//오른쪽으로 이동
//오른쪽에서 빼서 왼쪽에 넣어주기
if(!right.isEmpty()){
left.push(right.pop());
}
}else if(command.equals("B")){
//왼쪽 문자 삭제하기
if(!left.isEmpty())left.pop();
}else if(command.equals("P")){
//삽입 - 왼쪽에 넣으면 된다.
char word = st.nextToken().charAt(0);
left.push(word);
}
}
//왼쪽에 있는 값을 모두 오른쪽에 옮긴 다음에 출력하면 됨
StringBuilder sb = new StringBuilder();
while(!left.isEmpty())
right.push(left.pop());
while(!right.isEmpty())
bw.write(right.pop());
bw.flush();
bw.close();
}
}