표 편집 - Level 3
import java.util.Stack;
import java.util.StringBuilder;
class Solution {
public String solution(int n, int k, String[] cmd) {
int current = k;
// 삭제된 노드 보관하는 스택
Stack<Integer> deleted = new Stack<>();
// 해당 인덱스의 이전 노드, 첫 번재 인덱스는 이전 노드 없으므로 -1이 들어감
int[] prev = new int[n];
// 해당 인덱스의 이후 노드
int[] next = new int[n];
// 삭제 여부를 관리하는 배열
boolean[] removed = new boolean[n];
// 초기화
for(int i = 0; i < n; i++){
prev[i] = i - 1;
next[i] = i + 1;
}
// 마지막 인덱스는 이후 노드가 없으므로 -1을 넣어줌
next[n - 1] = -1;
int x;
for(String s: cmd){
String[] command = s.split(" ");
switch(command[0]){
case "U":
x = Integer.parseInt(command[1]);
for(int i = 0; i < x;i++) current = prev[current];
break;
case "D":
x = Integer.parseInt(command[1]);
for(int i = 0; i < x;i++) current = next[current];
break;
case "C":
deleted.push(current);
removed[current] = true;
if(prev[current]!= -1) next[prev[current]] = next[current];
if(next[current]!=-1) prev[next[current]] = prev[current];
current = (next[current]!=-1) ? next[current] : prev[current];
break;
case "Z":
if(!deleted.isEmpty()){
int restored = deleted.pop();
removed[restored] = false;
// 복구 시에는 양옆이 restored를 가리키게 해야 함
// 이전 인덱스의 next를 복구하려는 인덱스로 설정
if(prev[restored]!=-1) next[prev[restored]] = restored;
// 다음 인덱스의 prev를 복구하려는 인덱스로 설정
if(next[restored]!=-1) prev[next[restored]] = restored;
}
break;
}
}
StringBuilder sb = new StringBuilder();
for(boolean r: removed){
sb.append(r ? "X" : "O");
}
return sb.toString();
}
}
푼 방법
1. 초기화
- 이중 연결리스트를 구현했다.
Stack<Integer> deleted: 삭제된 노드를 보관하는 스택int[] prev: i번째 노드의 이전 값들을 보관하는 배열, 첫번째 노드는 이전 노드가 없으므로 -1을 넣는다.int[] next: i번째 노드의 다음 값들을 보관하는 배열, 마지막 노드는 다음 노드가 없으므로 -1을 넣는다.boolean[] removed: 최종 출력시에 삭제 여부 관리하는 배열
즉 prev,next는 연결 관계를 유지해야한다.
인덱스 이동
x만큼 위/아래로 현재 인덱스를 이동시킨다고 할 때, 반복문을 돌려서 prev과 next의 현재값을 하나씩 옮겨준다.
1 - 2 - 3 - 4지금 현재 인덱스가 1이고 2만큼 아래로 옮겨야 하면 반복문 한턴이 돌았을 때,
current가 이렇게 2번째 인덱스를 가리키려면 다음 인덱스를 가져가야 한다.
반대로 위로 옮기려면 이전 인덱스를 가져가야 한다. 그래서 위로 이동할 때는 prev, 아래로 이동할 때는 next를 사용해준다.
1 - 2 - 3 - 4
cur인덱스 삭제
이것도 간단하게 생각하면 삭제를 해주고 이어 붙여주면 된다.
1 - 2 - 3 - 4이렇게 있을 때 2를 삭제해야 한다고 가정해 보면,
1의 다음 인덱스를 3의 이전 인덱스로 설정해줘야 한다.
즉 next[prev[current]] 는 이전 인덱스의 다음 인덱스 값이므로, 이거를 삭제하려는 인덱스의 다음 값으로 바꿔준다.
이렇게만 해주면 [삭제노드] 의 이전 인덱스만 처리를 해준 것이다.
다음 인덱스의 prev 배열도 처리해주면 삭제 노드가 없어지고 이어붙여진다.
이렇게 값을 삭제하고 나서 stack에 push해줘야 한다. 영구적으로 삭제한 게 아니고 Z 명령어가 나오면 다시 넣어줘야 하기 때문이다.
removed에 true 처리도 해줘야 한다. 마지막 표시용으로..
// 이전 인덱스의 next 처리
if(prev[current]!= -1) next[prev[current]] = next[current];
// 다음 인덱스의 prev 처리
if(next[current]!=-1) prev[next[current]] = prev[current];인덱스 복구
인덱스 복구도 삭제랑 비슷한 느낌으로 구현하면 되는데,
이전 인덱스의 next와 다음 인덱스 prev가 복구하려는 인덱스를 가리키게 하면 된다.
먼저 삭제해둔 인덱스를 복구처리해준다. 가장 최근에 삭제된 인덱스를 stack에서 pop하고 removed 배열도 false처리해준다.
회고
- 처음에 연결리스트로 풀어서 간단하게 풀릴 줄 알았는데 시간초과가 났다 .. 다른 방법 찾아보니까 배열로 이중 연결리스트를 만드는 방법이 있어서 이렇게 하면 시간초과가 안날 것 같아서 시도해 봤다.
- 책에서는 마지막에 StringBuilder를 사용하지 않고 arrays fill 방법을 사용했다. 그다지 성능에 많은 차이가 날 것 같지는 않은데 StringBuilder를 남발하는 습관때문에 그런 것 같다. 최대한 util을 안쓰고 하는 방법을 항상 생각해봐야겠다.
- 책에서 switch case 말고 else if를 사용했는데 이것도 괜찮은 방법 같은게 C,Z는 숫자 매개변수가 딱히 없는 연산이라서.. 그렇지만 switch문이 뭔가 보기 깔끔해서 그냥 썼다.
