문제
입출력
구현 과정
1. ArrayList를 사용했을 때 (시간초과)
처음 문제를 보자마자
동적으로 값을 삽입하고 삭제할 수 있는 arrayList가 생각났다.
이를 활용하여 구현해봤더니 시간 초과가 떴다.
시간 초과인 이유는 데이터를 삽입하거나 삭제할 때마다 위치를 조정해줘야하는 점인 것 같다.
삽입과 삭제가 많은 이 문제에서 arrayList는 비효율적이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
//백준 1406번 에디터
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
String str = br.readLine();
String []strArr = str.split("");
int N = Integer.parseInt(br.readLine());
ArrayList<String> list = new ArrayList<String>(Arrays.asList(strArr));
int cursor = list.size(); //처음 커서 위치는 문자열의 끝 인덱스 + 1 임
for(int i = 0 ; i < N; i++){
st = new StringTokenizer(br.readLine(), " ");
switch (st.nextToken()){
case "P": //인덱스 cursor에 next.token삽입 list.add(cusor - 1, next.token)
if(cursor >= 0){
list.add(cursor, st.nextToken());
cursor += 1;
}
break;
case "L": //인덱스 커서 - 1
if(cursor > 0) {
cursor -= 1;
}else{
break;
}
break;
case "B": //인덱스 cursor -1 삭제 list.remove(cusor -1)
if(cursor > 0) {
list.remove(cursor - 1);
cursor -= 1;
}else{
break;
}
break;
case "D":
if(cursor < list.size()) {
cursor += 1;
}
break;
}
}
for( Object o : list){
System.out.print(o);
}
}
}2. LinkedList를 사용했을 때 (시간초과)
LinkedList는 내부적으로 양방향 연결리스트로 구성되어 있어 참조하혀려는 원소에 따라 처음부터 정방향 또는 역순으로 순회가 가능하다.
LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.
쉽게 말하자면 각 요소는 이전과 다음 요소의 정보를 가지고 있다.
그렇기에 ArrayList와 달리 임시 배열을 생성할 필요가 없고, 이전과 다음 요소의 정보를 활용하여 삽입/삭제를 처리할 수 있기에 유리하다.
하지만 결국 이 문제는 삽입/삭제가 빈번한데 더 빠른 처리를 요구하고 있다.
즉, 검색 시에는 인덱스를 통해 접근하는 것이 아니기에 최악의 경우는 모든 요소를 다 살펴봐야 하기 때문에 불리했다.
결국 ArrayList보다 유리하다고는 하나 결국 삽입/삭제 시 그 인덱스에 바로 접근하는 것이 아니라, head와 tail을 제외하곤 하나하나 살펴보며 찾아가서 처리하기 때문에 완전히 효율적이라고 볼 수 없다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
//백준 1406번 에디터
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String str = br.readLine();
int N = Integer.parseInt(br.readLine());
LinkedList<Character> list = new LinkedList<Character>();
for(int i = 0; i< str.length(); i++){
list.add(str.charAt(i));
}
int cursor = list.size(); //처음 커서 위치는 문자열의 끝 인덱스 + 1 임
for(int i = 0 ; i < N; i++){
String command = br.readLine();
char c = command.charAt(0);
switch (c){
case 'P': //인덱스 cursor에 next.token삽입 list.add(cusor - 1, next.token)
char t = command.charAt(2);
list.add(cursor, t);
cursor += 1;
break;
default:break;
case 'L': //인덱스 커서 - 1
if(cursor != 0) {
cursor -= 1;
}else{
break;
}
break;
case 'B': //인덱스 cursor -1 삭제 list.remove(cusor -1)
if(cursor != 0) {
list.remove(cursor - 1);
cursor -= 1;
}else{
break;
}
break;
case 'D':
if(cursor != list.size()) {
cursor += 1;
}
break;
}
}
for( Character o : list){
sb.append(o);
}
System.out.print(sb);
}
}구글링 후 방법을 알게 됨
https://minhamina.tistory.com/17
1. ListIterator (성공)
ListIterator는 Iterator를 상속한 인터페이스다.
Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.
그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//백준 1406번 에디터
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String str = br.readLine();
int N = Integer.parseInt(br.readLine());
LinkedList<Character> list = new LinkedList<Character>();
for(int i = 0; i< str.length(); i++){
list.add(str.charAt(i));
}
//iterator 메소드 호출
ListIterator<Character> iter = list.listIterator();
//처음 커서는 문장의 맨 뒤에 있어야하기 때문에 커서를 맨뒤로 이동시켜줌 (ex. abc|)
while(iter.hasNext()) {
iter.next();
}
for(int i = 0 ; i < N; i++){
String command = br.readLine();
char c = command.charAt(0);
switch (c){
case 'P': //인덱스 cursor에 next.token삽입 list.add(cusor - 1, next.token)
char t = command.charAt(2);
iter.add( t);
break;
default:break;
case 'L': //인덱스 커서 - 1
if(iter.hasPrevious())
iter.previous();
break;
case 'B': //인덱스 cursor -1 삭제 list.remove(cusor -1)
if(iter.hasPrevious()){
iter.previous();
iter.remove();
}
break;
case 'D':
if(iter.hasNext()){
iter.next();
}
break;
}
}
for( Character o : list){
sb.append(o);
}
System.out.print(sb);
}
}2. 스택 두개 사용 (성공)
스택은 모든 연산이 O(1)의 시간 복잡도를 가지기 때문에 시간 초과에 걸리지 않는다.
커서의 왼쪽 오른쪽 구분을 위해 두 개의 스택을 사용한다.
맨 처음 커서는 입력 문자열의 맨 뒤에 위치하기 때문에 문자열을 모두 왼쪽 스택에 넣어준다.
이후 차례로 명령어를 처리하면서 커서가 왼쪽으로 이동하면 왼쪽 스택의 가장 상단 요소를 오른쪽 스택에 pop() 시켜준다.
그리고 커서가 오른쪽으로 이동하면 오른쪽 스택의 가장 상단 요소를 왼쪽 스택에 pop() 시켜주며 마치 커서가 이동하는 것처럼 구현한다.
마지막 모든 명령어를 처리한 후에는 스택이 LIFO 구조이기 때문에 왼쪽 스택의 모든 요소들을 오른쪽 스택에 옮긴 후 오른쪽 스택을 모두 pop() 시키며 결과를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//백준 1406번 에디터
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String str = br.readLine();
int N = Integer.parseInt(br.readLine());
Stack<String> leftSt = new Stack<String>();
Stack<String> rightSt = new Stack<String>();
String[] arr = str.split("");
for (String s: arr){
leftSt.push(s);
}
for(int i = 0 ; i < N; i++){
String command = br.readLine();
char c = command.charAt(0);
switch (c){
case 'P': //인덱스 cursor에 next.token삽입 list.add(cusor - 1, next.token)
char t = command.charAt(2);
leftSt.push(String.valueOf(t));
break;
default:break;
case 'L': //인덱스 커서 - 1
if(!leftSt.isEmpty()){
rightSt.push(leftSt.pop());
}
break;
case 'B': //인덱스 cursor -1 삭제 list.remove(cusor -1)
if(!leftSt.isEmpty()){
leftSt.pop();
}
break;
case 'D':
if(!rightSt.isEmpty()){
leftSt.push(rightSt.pop());
}
break;
}
}
while(!leftSt.isEmpty())
rightSt.push(leftSt.pop());
//Stack은 LIFO 구조이기 때문에
//왼쪽 스택에 있는 데이터들을 모두 오른쪽으로 옮긴 뒤에 오른쪽에 있는 모든 내용을 출력한다.
while(!rightSt.isEmpty())
sb.append(rightSt.pop());
System.out.print(sb);
}
}
기본부터