처음 풀이
1. 커서를 포인터로 생각하여 현재 커서 위치에 해당하는 index값을 저장할 pointer 변수를 둔다.
2. StringBuilder에 문자열을 담아두고, StringBuilder 메서드인 deleteCharAt()과 insert()를 이용해 명령값과 현재 pointer 값에 따라 내부 문자열을 수정한다.
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder(bf.readLine());
//현재 문자열 맨 마지막에 커서 위치해야 한다.
int pointer = sb.length();
//명령어 갯수
int commandCnt = Integer.parseInt(bf.readLine());
for (int i = 0; i < commandCnt; i++) {
//현재 연산자
String commandLine = bf.readLine();
char command = commandLine.charAt(0);
switch (command) {
case 'L':
if (pointer != 0) {
pointer--;
}
break;
case 'D':
if (pointer != sb.length()) {
pointer++;
}
break;
case 'B':
if (pointer != 0) {
sb.deleteCharAt(--pointer);
}
break;
case 'P':
sb.insert(pointer++, commandLine.substring(2));
break;
}//switch case end
}//for end
System.out.println(sb);
}
아무래도 조건에서 초기 문자열 길이가 100,000이하이고, 입력할 수 있는 명령어의 수가 600,000개 이하이기 때문에 명령어 1개에 대한 처리 시간이 O(1)이어야 통과가 될 듯 싶었다.
deleteCharAt()과 insert() 내부를 보니 최소 O(1)은 넘을 거라 생각했다.
다른 풀이 (ListLiterator 사용)
나는 처음에 접근할 때 문자열 하나로 취급하여 해결하려고 했는데, 다른 풀이들을 보니까 O(1) 시간 복잡도를 위해 문자열을 문자 하나하나 찢어서 각각에 접근하려고 했다.
그래서 List에 각 문자를 저장하는데 요소를 추가, 삭제할 일이 많다보니 ArrayList보단 LinkedList로 구현했다.
하지만, LinkedList를 이용하고 pointer로 index를 정해 add()와 remove()를 이용해도 시간초과가 난다.
LinkedList에서는 ArrayList와 다르게 index로 접근한다고 하더라도 맨 앞과 맨 뒤 요소를 빼고 O(1)이 아닌 O(N)의 시간복잡도를 가지게 된다.
그래서 조금 더 찾아보니, 현재 위치를 매번 탐색하는 것이 아니라, 현재 위치에 커서가 머무르면서 명령어에 따라 커서를 이동하거나, 요소를 추가/삭제할 수 있는 방법으로 ListLiterator를 사용하고 있었다.
보통 Iterator는 컬렉션을 대상으로 단 방향으로만 탐색이 가능하다. 이러한 단점을 개선하고자 Iterator 인터페이스를 상속받아 여러 편의 기능을 추가한 ListIterator 인터페이스가 생겼다.
ListIterator 인터페이스를 사용하면 양 방향으로 탐색이 가능하다!
| 리턴 타입 | 메소드 | 설명 |
| void | add(E e) | 해당 리스트(list)에 전달된 요소를 추가함. (선택적 기능) |
| boolean | hasNext() | 이 리스트 반복자가 해당 리스트를 순방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함. |
| boolean | hasPrevious() | 이 리스트 반복자가 해당 리스트를 역방향으로 순회할 때 다음 요소를 가지고 있으면 true를 반환하고, 더 이상 다음 요소를 가지고 있지 않으면 false를 반환함. |
| E | next() | 리스트의 다음 요소를 반환하고, 커서(cursor)의 위치를 순방향으로 이동시킴. |
| int | nextIndex() | 다음 next() 메소드를 호출하면 반환될 요소의 인덱스를 반환함. |
| E | previous() | 리스트의 이전 요소를 반환하고, 커서(cursor)의 위치를 역방향으로 이동시킴. |
| int | previousIndex() | 다음 previous() 메소드를 호출하면 반환될 요소의 인덱스를 반환함. |
| void | remove() | next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 리스트에서 제거함. |
| void | set(E e) | next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 전달된 객체로 대체함. |
이를 이용해 풀어보면 다음과 같다,
public static void main2(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
LinkedList<Character> list = new LinkedList<>();
String original = bf.readLine();
int length = original.length();
//초기 문자열을 문자로 나눠 list에 저장
for (int i = 0; i < length; i++) {
list.add(original.charAt(i));
}//for end
//명령어 갯수
int commandCnt = Integer.parseInt(bf.readLine());
//list 탐색할 listIterator
ListIterator<Character> listIterator = list.listIterator();
//커서 위치를 맨 마지막으로
while (listIterator.hasNext()) {
listIterator.next();
}//while end
for (int i = 0; i < commandCnt; i++) {
//현재 연산자
String commandLine = bf.readLine();
char command = commandLine.charAt(0);
switch (command) {
case 'L' :
if (listIterator.hasPrevious()) {
listIterator.previous();
}
break;
case 'D' :
if (listIterator.hasNext()) {
listIterator.next();
}
break;
case 'B' :
if (listIterator.hasPrevious()) {
/**
* next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 리스트에서 제거하기 때문에
* 제거 전에 커서를 왼쪽으로 한 칸 이동(previous())
*/
listIterator.previous();
listIterator.remove();
}
break;
case 'P' :
listIterator.add(commandLine.charAt(2));
break;
}
}//for end
//최종 문자열 담을 StringBuilder
StringBuilder sb = new StringBuilder();
for (Character c : list) {
sb.append(c);
}//for end
System.out.println(sb);
}
다른 풀이 (두 Stack 사용)
문자열을 문자로 하나하나 나눠서 생각하는 방식은 같다. 여기서 자료구조 중에 Stack을 사용한 풀이가 있다.
현재 커서 위치를 기준으로 왼쪽, 오른쪽 문자를 두 Stack에 나눠 담는 것이다.
그리고 커서가 이동하면 한쪽 Stack에서 pop해서 다른 요소에 push하고, 문자를 삭제/추가할 때는 왼쪽 stack에 pop/push 해주면 된다. Stack에서 pop / push는 O(1)의 시간복잡도를 가지기 때문에 충분히 통과가능하다.
코드로 풀어보면 다음과 같다.
public static void main3(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//커서 위치를 기준으로 문자 담을 Stack 2개
Stack<Character> leftStk = new Stack<>();
Stack<Character> rightStk = new Stack<>();
String original = bf.readLine();
int length = original.length();
//왼쪽 Stack에 문자를 전부 담는다. (맨 처음 커서 위치가 문자열 맨 뒤기 때문에)
for (int i = 0; i < length; i++) {
leftStk.push(original.charAt(i));
}//for end
//명령어 갯수
int commandCnt = Integer.parseInt(bf.readLine());
for (int i = 0; i < commandCnt; i++) {
//현재 연산자
String commandLine = bf.readLine();
char command = commandLine.charAt(0);
switch (command) {
case 'L' :
if (!leftStk.isEmpty()) {
//커서 왼쪽 이동 -> 왼쪽 Stack 요소 pop해서 오른쪽 Stack에 push
rightStk.push(leftStk.pop());
}
break;
case 'D' :
if (!rightStk.isEmpty()) {
//커서 오른쪽 이동 -> 오른쪽 Stack 요소 pop해서 왼쪽 Stack에 push
leftStk.push(rightStk.pop());
}
break;
case 'B' :
if (!leftStk.isEmpty()) {
//커서 왼쪽 문자 제거 -> 왼쪽 Stack에서 pop
leftStk.pop();
}
break;
case 'P' :
//커서 왼쪽으로 문자 추가 -> 왼쪽 Stack에 요소 push
leftStk.push(commandLine.charAt(2));
break;
}
}//for end
//앞 문자부터 출력하기 위해 오른쪽 Stack으로 전부 이동
while (!leftStk.isEmpty()) {
rightStk.push(leftStk.pop());
}//while end
StringBuilder sb = new StringBuilder();
while (!rightStk.isEmpty()) {
sb.append(rightStk.pop());
}//while end
System.out.println(sb);
}
사실 StringBuilder로만 풀 생각이 들었고, 시간초과가 나와서 어떻게 해야할지 몰랐다.
내부 연산이 O(1)이 되기 위해 문자열을 문자로 나눠서 고민하고, 이를 처리하는 과정에서 LinkedList 탐색 시간복잡도에 복습할 수 있었고, 양방향 탐색이 가능한 ListIterator을 공부하고 써볼 수 있었고, 또, Stack 자료구조에 대한 연습을 할 수 있었다.
참고
https://minhamina.tistory.com/18
'자료구조 & 알고리즘 > 문제풀이' 카테고리의 다른 글
| 기타리스트 - 백준 1495 (Java) (0) | 2022.05.22 |
|---|---|
| 창고 다각형 - 백준 2304 (Java) (0) | 2022.05.19 |
| 순위검색 - 프로그래머스 (Java, Level 2) (0) | 2022.05.02 |
| 거리두기 확인하기 - 2021 카카오 채용연계형 인턴십 (Java, Level 2) (0) | 2022.04.30 |
| 메뉴 리뉴얼 - 프로그래머스 (Java, Level 2) (0) | 2022.04.29 |
댓글