📝 문제
💡 풀이 과정
⛓ 사용한 자료구조 : LinkedList(연결리스트)
특별히 복잡한 알고리즘이나 자료구조를 쓴다기 보다는 조건에 맞게 충실하게 구현하면 되는 문제이다. 다만 시간초과가 발생할 수 있으니 적절한 자료구조를 사용해서 푸는 것이 중요한 것 같다.
1차 시도: 시간 초과
문제를 보고 사용해야겠다고 생각한 자료구조는 LinkedList(연결리스트) 였다. ArrayList와 달리 연결리스트는 인접 참조를 통해 체인처럼 리스트 요소를 관리하는 것으로 알고 있었고, 때문에 삽입/삭제가 빈번한 문제의 경우 일반 리스트보다 연결리스트를 사용하는 것이 인덱스를 관리하기도 수월할 것이라고 생각했다.
따라서 현재 위치를 나타내는 변수 temp 를 선언하여 매번 위치가 변경될 때마다 변수의 값을 갱신시키고, 연산을 수행할 때는 해당 변수의 값으로 수행 위치를 찾아가는 방식을 사용했다.
그런데 사실 연결리스트가 일반적인 리스트보다 유리하긴 하지만 결국 삽입/삭제할 때 해당 위치에 인덱스를 가지고 바로 접근하는 것이 아니고 head 와 tail 을 제외하고는 하나씩 살펴보면서 찾아가는 방식으로 리스트 요소에 접근한다.
즉, 최악의 경우에는 리스트에 있는 모든 요소를 하나씩 살펴볼 수도 있는거죠!
결국 삽입/삭제 연산을 최적화할 수 있는 방법을 새로 찾아야 하는 상황에 도달했다.
2차 시도: ListIterator 사용
삽입/삭제 연산을 최적화하려면 결국 리스트 내 원하는 위치에 빠르게 도착할 수 있어야 한다. 해당 부분을 찾다가 ListIterator 라는 녀석을 발견했다! 두둥
ListIterator는 우리가 잘 알고 있는 Java의 Iterator 인터페이스를 상속한 인터페이스로, 단방향 탐색만 가능했던 Iterator 와 달리 양방향 탐색이 가능 하다. JDK 1.2 부터 제공되고, 이름에서부터 알 수 있듯이 List 인터페이스를 구현한 컬렉션에서만 사용 가능하다고 한다.
자세한 설명과 관련 메소드는 아래 공식문서를 참고했습니다.
ListIterator - Java Reference
커서를 앞/뒤로 움직여야 하고, 연결리스트를 활용하는 이번 문제에서 유용하게 사용될 수 있을 것이다! ListIterator에서 제공하는 previous() , next() , remove() , hasNext() 등을 잘 활용하면 쉽게 구현이 가능하다.
다만 remove() 메소드를 사용할 때 주의할 점이 있다. remove() 는 next() 또는 previous() 에 의해 리턴된 가장 마지막 요소를 제거한다. 따라서 이전에 요소가 있는지 확인한 후에는 꼭 previous() 함수를 호출해 이전 요소로 이동한 후에 리스트에서 해당 요소를 제거해줘야 한다. 이동하지 않고 함수를 호출하면 엉뚱한 요소를 지워버릴 수 있으니 주의!
코드
package day0606;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String origin = br.readLine();
int M = Integer.parseInt(br.readLine());
LinkedList<Character> list = new LinkedList<>();
for(int i=0;i<origin.length();i++) {
list.add(origin.charAt(i));
}
ListIterator<Character> iter = list.listIterator();
while(iter.hasNext()) { //맨 뒤로 보내기(초기 커서 위치)
iter.next();
}
for(int m=0;m<M;m++) {
String str = br.readLine();
char op = str.charAt(0);
if(op=='P') {
char target = str.charAt(2);
iter.add(target);
} else if(op=='L') {
if(iter.hasPrevious())
iter.previous();
} else if(op=='D') {
if(iter.hasNext())
iter.next();
} else if(op=='B') {
if(iter.hasPrevious()) {
iter.previous();
iter.remove();
}
}
}
StringBuilder sb = new StringBuilder();
for(char c: list) {
sb.append(c);
}
System.out.println(sb.toString());
}
}
