문제
접근
1. LinkedList
단순히 리스트 중간에 값을 추가하거나 빼주는 연산이 빈번하게 발생할 수 있기 때문에, LinkedList로 구현하는 것이 빠르겠다고 생각했다.
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
List<String> list = new LinkedList<>();
for(char ch : str.toCharArray()) {
String separatedStr = String.valueOf(ch);
list.add(separatedStr);
}
int cursor = str.length();
int nums = Integer.parseInt(br.readLine());
for(int i=0; i<nums; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String command = st.nextToken();
switch(command) {
case "L" :
if(cursor > 0) {
cursor--;
}
break;
case "D" :
if(cursor < list.size()) {
cursor++;
}
break;
case "B" :
if(cursor > 0) {
list.remove(--cursor);
}
break;
default :
list.add(cursor, st.nextToken());
cursor++;
}
}
StringBuilder sb = new StringBuilder();
for(String s : list) {
sb.append(s);
}
br.close();
System.out.println(sb.toString());
}
}실행 결과, 시간 초과로 인해 실패했다.
원인을 알아보기 위해, LinkedList 클래스 내부에 add(int index, E e)와 remove(int index)가 어떻게 동작하는지 확인해봤다.
add(int index, E e)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}rmove(int index)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}위 코드가 실제 LinkedList 내 구현된 add와 remove이다. 공통적으로 index가 LinkedList index 내에 존재하는 index 인지 확인한다.(checkPositionIndex(index))
그 다음으로 인덱스에 해당하는 Node를 찾는 메소드가 호출된다.(node(index)) 이 메소드의 내부 동작을 살펴보면 다음과 같다.
node(int index)
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}결국, 중간에서 요소를 추가/제거하기 위해서는 0부터 순차적으로 index에 해당하는 node의 이전과 이후의 node 번호를 조회해줘야 한다.
이 로직의 탐색 과정은 시간 복잡도 O(n)으로, 최악의 경우 list의 크기 또는 하나 작은 크기의 탐색이 추가/삭제 시마다 수행된다.
이러한 구현 로직으로 인해, LinkedList로 add 또는 remove를 수행하게 되면, 해당 로직에서 시간초과가 났을것 같다.
그렇다면, 어떤 자료구조를 사용해야 이를 효율적으로 처리할 수 있을까?
2. ListIterator
ChatGPT에게 물어보았다.
Iterator 사용
1. Iterator는 현재 위치를 가리키는 포인터를 직접 조작합니다.
2. ListIterator를 사용하면 양방향 이동이 가능하며, 현재 위치에서 요소를 추가하거나
삭제할 수 있습니다.
3. 원하는 위치까지 이동한 후, 추가나 삭제 연산을 수행합니다.
4. 이 경우 포인터 조정만으로 요소를 추가하거나 삭제할 수 있어 효율적입니다.즉, 포인터를 직접 조작하기 때문에, 불필요한 탐색 시간이 줄어든다고 한다. 이로 인해 O(1)의 시간복잡도로 추가/삭제 수행이 가능하다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
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 str = br.readLine();
List<String> list = new LinkedList<>();
for(char ch : str.toCharArray()) {
String separatedStr = String.valueOf(ch);
list.add(separatedStr);
}
int nums = Integer.parseInt(br.readLine());
ListIterator<String> iter = list.listIterator(list.size());
for(int i=0; i<nums; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String command = st.nextToken();
switch(command) {
case "L" :
if(iter.hasPrevious()) {
iter.previous();
}
break;
case "D" :
if(iter.hasNext()) {
iter.next();
}
break;
case "B" :
if(iter.hasPrevious()) {
iter.previous();
iter.remove();
}
break;
default :
iter.add(st.nextToken());
}
}
StringBuilder sb = new StringBuilder();
for(String s : list) {
sb.append(s);
}
System.out.println(sb.toString());
br.close();
}
}위처럼 LinkedList 객체 내 메소드가 아닌 ListIterator 인터페이스로 정의된 방식으로 메서드를 실행해보니 정상적으로 통과되었다.
실제로 대략 100개 정도의 테스트 케이스로 로직 수행시간을 계산해본 결과 다음과 같이 수행시간이 차이가 난다.
LinkedList
ListIterator
대략 12배 정도 차이나는걸로 봐서는 중간에 삽입 또는 삭제하는 로직이 필요한 경우, LinkedList와 ListIterator 조합으로 사용하는 것이 수행 속도 측면에서 훨씬 빠를것 같습니다.
제출
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
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 str = br.readLine();
List<String> list = new LinkedList<>();
for(char ch : str.toCharArray()) {
String separatedStr = String.valueOf(ch);
list.add(separatedStr);
}
int nums = Integer.parseInt(br.readLine());
ListIterator<String> iter = list.listIterator(list.size());
for(int i=0; i<nums; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String command = st.nextToken();
switch(command) {
case "L" :
if(iter.hasPrevious()) {
iter.previous();
}
break;
case "D" :
if(iter.hasNext()) {
iter.next();
}
break;
case "B" :
if(iter.hasPrevious()) {
iter.previous();
iter.remove();
}
break;
default :
iter.add(st.nextToken());
}
}
StringBuilder sb = new StringBuilder();
for(String s : list) {
sb.append(s);
}
System.out.println(sb.toString());
br.close();
}
}
백엔드 서버 엔지니어