표 편집

문제

프로그래머스

행 번호가 적혀있는 표가 주어지면 여러 명령어를 통해 표를 삽입하거나 삭제할 수 있다.

명령어 모음인 cmd가 주어지면 처음에 주어진 표와 cmd 명령이 모두 실행된 후의 표와 비교해 원래에 표와 동일한 행이면 O, 다르면 X를 표시해 문자열을 return 하는 문제이다.

 

먼저 주어진 n은 원래 주어진 표의 길이이다. 예를들어  n = 8이라고 하면 행번호는 (0 ~ 7) 이된다.

k는 현재 선택된 행 번호를 의미한다. cmd는 다음과 같이 4가지 종류로 나눠진다.

"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.

"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.$

"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.

"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

 

처음에 주어진 n = 8이고, k = 2로 주어지면 맨 왼쪽 그림과 같다.

여기서 "D 2"를 수행하고 "C"를 수행하면 아래 그림과 같다.

여기서 "U 3"를 수행한 다음 "C"를 수행하면 왼쪽 그림과 같다.

그 다음 "D 4"를 수행하고 "C"를 수행하면 오른쪽 그림과 같다ㅏ.

다음으로 "U 2"를 수행하면 왼쪽 그림과 같다.

여기서 "Z"를 수행하면 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구된다. 가운데 그림이다.

여기서 또 다시 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 복구된다. 오른쪽 그림이다.

이때, 현재 선택된 행은 바뀌지 않는다.

최종적으로 아래 그림과 같다. 비교를 통해 "OOOOXOOO" 를 return 하면 된다.

---

처음에는 표 자체를 ArrayList로 만들어 삭제와 삽입이 동적으로 이루어지는 자료구조를 사용했다.

하지만 원래 있던 표에서 이전 행번호와 다음 행번호를 기억해 놔야 제대로 답을 구할 수 있었다.

따라서 이전 행 번호와 다음 행 번호를 기억하기 위해 LinkedList 형태로 데이터를 저장하였다.

class Node{
    int pre;
    int cur;
    int nxt;
    Node(int pre, int cur, int nxt){
        this.pre = pre;
        this.cur = cur;
        this.nxt = nxt;
    }
}

여기서 0번 행의 이전 행번호는 -1로 설정하고 마지막 행번호의 다음 행번호는 -1로 설정한다.

int []pre =new int[n];
        int []next = new int[n];
        for(int i=0;i<n;i++){
            pre[i] = i-1;
            next[i] = i+1;
        }
        next[n-1] = -1;

삭제된 데이터는 stack을 이용해 저장해둔다.

StringBuilder를 활용해 처음에 모두 "O"으로 n개를 채운다.

Stack<Node>stack = new Stack<>();
StringBuilder sb = new StringBuilder("O".repeat(n));

이제 cmd 배열을 돌아보면서 각 명령에 해당하는 로직을 처리해준다.

for(int i=0;i<cmd.length;i++){
            char ch = cmd[i].charAt(0);
            if(ch == 'U'){
                //두자리 숫자가 올 수 있으므로...
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num -- > 0){
                    k = pre[k];
                }
            }
            else if(ch =='D'){
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num -- > 0){
                    k = next[k];
                }
            }
            else if(ch == 'C'){
                stack.push(new Node(pre[k], k, next[k]));
                if(pre[k] != -1)next[pre[k]] = next[k];
                if(next[k] != -1)pre[next[k]] = pre[k];
                sb.setCharAt(k, 'X');
                
                if(next[k] != -1)k = next[k];
                else k = pre[k];
            }
            else if (ch == 'Z'){
                Node node = stack.pop();
                if(node.pre != -1)next[node.pre] = node.cur;
                if(node.nxt != -1)pre[node.nxt] = node.cur;
                sb.setCharAt(node.cur, 'O');
            }
        }

 

U와 D는 단순히 행 이동만 하면 된다.

C가 나오면 현재 LinkedList에서 k가 가리키는 노드를 삭제하고 k가 가리키는 노드의 이전 노드와 다음 노드를 서로 연결해

줘야 한다.

따라서 k가 가리키는 노드의 이전 노드의 다음 노드를 k가 가리키는 노드의 다음 노드를 가리키게 한다.

마찬가지로 k번째 노드의 다음 노드의 이전 노드를 k가 가리키는 노드의 이전 노드를 가리키게 한다.

 

Z가 나오면 다시 되돌려 놓아야 한다.

 

---

전체 코드이다.

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        int []pre =new int[n];
        int []next = new int[n];
        for(int i=0;i<n;i++){
            pre[i] = i-1;
            next[i] = i+1;
        }
        next[n-1] = -1;
        
        Stack<Node>stack = new Stack<>();
        StringBuilder sb = new StringBuilder("O".repeat(n));
        for(int i=0;i<cmd.length;i++){
            char ch = cmd[i].charAt(0);
            if(ch == 'U'){
                //두자리 숫자가 올 수 있으므로...
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num -- > 0){
                    k = pre[k];
                }
            }
            else if(ch =='D'){
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num -- > 0){
                    k = next[k];
                }
            }
            else if(ch == 'C'){
                stack.push(new Node(pre[k], k, next[k]));
                if(pre[k] != -1)next[pre[k]] = next[k];
                if(next[k] != -1)pre[next[k]] = pre[k];
                sb.setCharAt(k, 'X');
                
                if(next[k] != -1)k = next[k];
                else k = pre[k];
            }
            else if (ch == 'Z'){
                Node node = stack.pop();
                if(node.pre != -1)next[node.pre] = node.cur;
                if(node.nxt != -1)pre[node.nxt] = node.cur;
                sb.setCharAt(node.cur, 'O');
            }
        }
        
        return sb.toString();
    }
}
class Node{
    int pre;
    int cur;
    int nxt;
    Node(int pre, int cur, int nxt){
        this.pre = pre;
        this.cur = cur;
        this.nxt = nxt;
    }
}

---

구글링을 하면 아래와 같은 코드도 존재한다.

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> stack = new Stack<>();
        int tableSize = n;
        
        for(int i=0;i<cmd.length;i++){
            char c = cmd[i].charAt(0);
            if(c == 'D')
                k+=Integer.parseInt(cmd[i].substring(2));
            else if(c=='U')
                k-=Integer.parseInt(cmd[i].substring(2));
            else if(c=='C'){
                stack.add(k);
                tableSize--;
                if(k==tableSize)
                    k--;
            }
            else if(c=='Z'){
                if(stack.pop() <= k)k++;
                tableSize++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<tableSize;i++)
            sb.append("O");
        while(!stack.isEmpty())
            sb.insert(stack.pop().intValue(),"X");
        return sb.toString();  
    }
}