문제 설명
앙몬드가 표를 편집한다고 한다. D는 커서를 위로 올리고 U는 커서를 아래로 내리며 C는 해당 커서가 가리키는 부분을 지우고 Z는 가장 최근에 삭제한 값을 예전 위치로 돌린다고 한다. 이때, 표에 존재하면 'O'를 존재하지 않으면 'X'를 표시해서 반환하라.
링크드리스트 문제라고 생각했지만, 스택으로도 풀 수 있지 않을까 싶어서 먼저 스택으로 풀어봤다. 테스트를 몇 개는 통과하고 또 몇 개는 틀리고 시간 초과, 런타임 에러가 나서 링크드 리스트로 돌아갔지만...
아이디어는 얻었지만 그 과정을 몰라 답을 보니 배열 두 개를 이용하더라. pre에는 노드 i의 앞에 연결되어 있는 값을 넣고 next에는 노드 i의 뒤에 연결되어 있는 값을 넣어준다.
여기서도 스택이 사용되기는 하지만, 스택은 지워진 값을 넣을 때만 쓴다. 그 이유는 가장 최근에 지워진 값을 가지고 와야 하기 때문이다.
코드 설명
- Node class, k의 앞의 값과 k 그리고 k의 뒤의 값을 저장하는 클래스. 삭제할 때 필요하다.
-
필요한 변수
1-1. pre 배열, 노드 i의 앞에 연결 되어 있는 노드를 표시하는 값
1-2 next 배열, 노드 i의 뒤에 연결 되어 있는 노드를 표시하는 값
1-3 Stack stack, 복구할 때는 최근에 지운 값부터 차례대로 가지고 오니까 스택에 저장
1-4 StringBuilder sb, 반환할 문장. -
pre와 next에 먼저 값을 넣어야 한다. pre에는 i 앞에 연결되는 값을, next에는 i 뒤에 연결되는 값을 넣는데 맨 첫 번째 값과 맨 마지막 값에는 연결되지 않았음을 표시하는 -1을 넣어야 한다.
-
명령어를 차례대로 진행한다.
3-1 명령어 'U', k를 위로 올려야 하니 주어진 숫자 만큼 k의 pre 값을 k에 넣는다.
3-2 명령어 'D', k를 뒤로 내려야 하니 주어진 숫자 만큼 k의 next 값을 k에 넣는다.
3-3 명령어 'C', k가 가리키는 값을 삭제해야 하니 stack에 k의 pre 값, k, k의 next 값을 넣어준다. 그리고 k의 앞에 있는 값과 뒤에 있는 값을 연결해줘야 한다.
만일 k가 맨 앞의 값이 아니라면 k의 pre값의 next를 k의 next와 연결해야 한다. 또한 만일 k가 맨 뒤의 값이 아니라면 k의 next값의 pre를 k의 pre와 연결해야 한다.
그리고 k를 하나 내려줘야 하는데, 만일 맨 마지막 값을 삭제해서 내릴 곳이 없다면 하나 올려준다.
또한 값을 삭제했으니 문자열의 해당 위치에 있는 값을 'X'로 바꾼다.
3-4 명령어 'Z', 가장 마지막에 삭제했던 값을 원래 위치로 돌려줘야 한다. 맨 처음이 아니라면 돌려 놓을 값을 해당 값의 pre의 next에 넣어준다. 그리고 맨 마지막이 아니라면 돌려 놓을 값을 해당 값의 next의 pre에 넣어준다.
마지막으로 값을 넣어줬으니 문자열의 해당 위치에 있는 값을 'O'로 바꾼다. -
모든 명령어가 끝이 나면 sb를 String으로 반환해 return하면 된다.
코드
import java.util.*;
class Node{
int pre;
int cur;
int next;
public Node(int pre, int cur, int next){
this.pre = pre;
this.cur = cur;
this.next = next;
}
}
class Solution {
public String solution(int n, int k, String[] cmd) {
int[] pre = new int[n];
int[] next = new int[n];
//pre[i], 노드 i의 앞에 있는 노드
//next[i], 노듸 i의 뒤에 있는 노드
//맨 앞의 앞 노드와 맨 뒤의 뒤 노드는 -1로 넣어준다.
for(int i=0; i<n; i++){
pre[i] = i-1;
next[i] = i+1;
}
next[n-1] = -1;
//지운 값을 넣는 stack
Stack<Node> stack = new Stack<>();
StringBuilder sb = new StringBuilder("O".repeat(n));
//명령을 차례대로 진행시킨다.
for(int i=0; i<cmd.length; i++){
String[] s = cmd[i].split(" ");
String order = s[0];
if(order.equals("U")){
//위로 올라가야 할 때는 k의 값을 하니씩 앞으로 옮긴다.
int num = Integer.parseInt(s[1]);
while(num > 0){
k = pre[k];
num--;
}
}else if(order.equals("D")){
//아래로 내려가야 할 때는 k의 값을 하나씩 뒤로 옮긴다.
int num = Integer.parseInt(s[1]);
while(num > 0){
k = next[k];
num--;
}
}else if(order.equals("C")){
//삭제할 값(k의 앞에 있는 값, k, k의 뒤에 있는 값)을 스택에 넣어준다.
stack.push(new Node(pre[k], k, next[k]));
//맨 앞에 있는 숫자가 아니라면 k의 앞에 있는 숫자의 next(원래 k가 있던 자리)에는 k의 next가 들어가야 한다.
if(pre[k] != -1){
next[pre[k]] = next[k];
}
//맨 뒤에 있는 숫자가 아니라면 k의 뒤에 있는 숫자의 pre(원래 k가 있던 자리)에는 k의 pre가 들어가야 한다.
if(next[k] != -1){
pre[next[k]] = pre[k];
}
//k가 지워졌으므로 해당 k의 위치에 'X'로 값을 넣는다.
sb.setCharAt(k, 'X');
//k가 맨 마지막이 아니라면 k는 한 칸 뒤로 내려간다.
if(next[k] != -1){
k = next[k];
}else{
//k가 맨 마지막이라면 k는 한 칸 올라간다.
k = pre[k];
}
}else if(order.equals("Z")){
//가장 최근에 삭제한 값을 하나 불러온다.
Node node = stack.pop();
if(node.pre != -1){
//삭제한 값이 제일 먼저 있지 않다면 해당 노드 앞에 있던 값의 뒤(원래 있었던 곳)에 값을 넣어준다.
next[node.pre] = node.cur;
}
if(node.next != -1){
//삭제한 값이 맨 마지막에 있지 않다면 해당 노드의 뒤에 있는 노드의 앞에 값에 다시 값을 넣어준다.
pre[node.next] = node.cur;
}
//해당 값에 'O'을 넣는다.
sb.setCharAt(node.cur, 'O');
}
}
return sb.toString();
}
}여담
스택은 넣고 빼는 시간 복잡도가 O(1)이기 때문에 시간 초과에 걸리지 않을 거라고 생각했지만, 넣다 뺐다를 반복문으로 여러 번 돌려야 하기 때문에 시간 초과가 난다. 내가 놓친 부분도 있을 테고.
또한 링크드 리스트를 이렇게 배열로 쓰는 것도 다시 배웠다. 분명 예전에 배웠지만, 잊어버린 건가... 다시 알았으니까 다행이다.
코드가 아까우니까 스택을 이용한 코드는 여기에다가 적어 놓겠다.
엄청 길다
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
Stack<Integer> delete = new Stack<>();
int current = 0;
int num = 0;
int count = 0;
for(int i=0; i<k; i++){
s2.push(i);
}
for(int i=n-1; i>=k; i--){
s1.push(i);
}
for(String s : cmd){
String[] tmp = s.split(" ");
String order = tmp[0];
if(order.equals("D")){
num = Integer.parseInt(tmp[1]);
for(int i=0; i<num; i++){
if(!s1.isEmpty()){
s2.push(s1.pop());
}
}
}else if(order.equals("U")){
num = Integer.parseInt(tmp[1]);
for(int i=1; i<=num; i++){
if(!s2.isEmpty()){
s1.push(s2.pop());
}
}
}else if(order.equals("C")){
int tmpNum = s1.pop();
delete.push(tmpNum);
if(s1.isEmpty()){
s1.push(s2.pop());
}
}
else if(order.equals("Z")){
int addNum = delete.pop();
int tmpNum = 0;
Stack<Integer> s3 = new Stack<>();
if(!s1.isEmpty()){
if(s1.peek() < addNum){
while(true){
if(s1.isEmpty() || s1.peek() > addNum){
break;
}
s3.push(s1.pop());
}
s1.push(addNum);
while(!s3.isEmpty()){
s1.push(s3.pop());
}
}else if(s1.peek() > addNum){
if(s2.isEmpty() || s2.peek() < addNum){
s2.push(addNum);
}else{
while(true){
if(s2.peek() < addNum || s2.isEmpty()){
break;
}
s3.push(s2.pop());
}
s2.push(addNum);
while(!s3.isEmpty()){
s2.push(s3.pop());
}
}
}
}
}
}
while(!s2.isEmpty()){
s1.push(s2.pop());
}
int idx = 0;
StringBuilder sb = new StringBuilder();
while(!s1.isEmpty()){
int tmpNum = s1.pop();
if(tmpNum == idx){
sb.append("O");
}else{
s1.push(tmpNum);
sb.append("X");
}
idx++;
}
return sb.toString();