https://school.programmers.co.kr/learn/courses/30/lessons/81303
문제 해답에서 알아 두면 좋을 수 있는 내용이 있어 작성한다.
(정수 배열 2개를 이용한 LinkedList 구현)
0~n-1까지 유저가 있고, 커서가 k번째에 위치한 상태로 시작한다.
표에 대한 명령어는 4가지가 존재한다.
- U X -> 커서를 위로 X칸만큼 올린다
- D X -> 커서를 아래로 X칸만큼 올린다
- C -> 현재 커서에 위치하는 유저를 삭제한다.
유저를 삭제한 뒤 다음 유저가 삭제된 위치로 오게 되며 커서 값은 그대로.
마지막 유저를 삭제한 경우, 삭제 이후 마지막이 된 유저로 커서가 옮겨진다. - Z -> 가장 최근 삭제한 유저를 복구한다. 커서는 옮기지 않는다.
문제를 처음 접근할 때 추가, 삭제에 대한 연산이 많은 경우를 생각해 LinkedList를 사용해 풀이해 보려고 했다.
하지만 java.util에서 제공하는 LinkedList는 Node를 직접 손대는 것이 불가능해 원하는 연산을 할 수 없었다.
n도 최대 1,000,000이고 연산 개수도 최대 200,000개라 손대기가 어려워 다른 사람의 코드를 참고했는데 일반 배열 2개를 이용한 LinkedList를 구현하는 방법이 있었다.
원리는 다음과 같다.
이전 노드를 나타내는 Prev 배열과 다음 노드를 나타내는 Next 배열 2개를 만들고, 현재 노드들을 연결한다. (이전 or 다음이 없다면 -1 표시)
예시를 들기 위해, 2번 노드에 대한 연결 관계를 알아보자.
Prev[2] = 1로, 2번 노드의 앞에는 1번 노드가 있음을 의미한다.
Next[2] = 3으로 2번 노드의 다음에는 3번 노드가 있음을 의미한다.
그럼 본격적으로, 2번 노드를 예시로 삭제 과정을 먼저 알아보자.
2번 노드는 앞에 1번, 뒤에 3번 노드가 붙어있는 구조이다.
2번 노드가 사라지면 1번 노드의 다음을 3번으로, 그리고 3번 노드의 앞을 1번으로 바꿔주어야 한다.
이런 식으로 말이다.
코드로 나타내보자면 아래와 같은 과정이 될 것이다.
// 현재 위치 cursor
val prevNum = prev[cursor]
val nextNum = next[cursor]
next[prevNum] = nextNum
prev[nextNum] = prevNum이후 cursor를 다음 위치로 이동시켜 주면 된다. (cursor가 마지막인 경우 이전 위치로)
또한 이 문제에는 되돌리기 기능이 존재한다.
따라서 스택에 삭제한 숫자와 그 앞뒤 원소에 대한 정보를 넣어 복구하는 경우 바로 추가할 수 있도록 한다.
data class Removed(
val n: Int,
val prev: Int,
val next: Int
)나는 Removed라는 클래스를 하나 생성하여 복구에 필요한 정보를 다루었다.
다시 삭제했던 예시를 가지고 복구하는 과정을 생각해 보자.
2번 원소를 삭제하였으며, Removed(2, 1, 3) 상태로 스택에 존재할 것이다.
복구는 삭제보다 간단하다.
기존 2의 이전 노드인 1의 다음 노드를 2로, 다음 노드인 3의 이전 노드를 2로 다시 고쳐주면 된다.
val recent = removed.pop()
val prevNum = recent.prev
val nextNum = recent.next
next[prevNum] = recent.n
prev[nextNum] = recent.n코드로 나타내 보면 위와 같다.
Up과 Down에 대한 작동은 간단하다.
U X 명령이 들어오면 X번 만큼 prev배열을 보며 이전 칸으로 이동하면 되고
D X 명령이 들어오면 X번 만큼 next배열을 보며 다음 칸으로 이동하면 된다.
class Solution {
fun solution(n: Int, k: Int, cmd: Array<String>): String {
val prev = IntArray(n){it - 1}
val next = IntArray(n){it + 1}
next[n - 1] = -1
val removed = Stack<Removed>()
val answer = CharArray(n){'O'}
var cursor = k
for(command in cmd){
val c = command.split(' ')
when(c[0][0]){
'D' -> {
for(i in 1..c[1].toInt()){
if(next[cursor] == -1) break
cursor = next[cursor]
}
}
'U' -> {
for(i in 1..c[1].toInt()){
if(prev[cursor] == -1) break
cursor = prev[cursor]
}
}
'C' -> {
removed.add(Removed(cursor, prev[cursor], next[cursor]))
val prevNum = prev[cursor]
val nextNum = next[cursor]
if(prevNum != -1)
next[prevNum] = nextNum
if(nextNum != -1)
prev[nextNum] = prevNum
answer[cursor] = 'X'
cursor = if(nextNum == -1) prevNum else nextNum
}
'Z' -> {
val recent = removed.pop()
val prevNum = recent.prev
val nextNum = recent.next
if(prevNum != -1)
next[prevNum] = recent.n
if(nextNum != -1)
prev[nextNum] = recent.n
answer[recent.n] = 'O'
}
}
}
return String(answer)
}
}
data class Removed(
val n: Int,
val prev: Int,
val next: Int
)