표 편집

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

제한사항
5 ≤ n ≤ 1,000,000
0 ≤ k < n
1 ≤ cmd의 원소 개수 ≤ 200,000
정확성 테스트 케이스 제한 사항
5 ≤ n ≤ 1,000
1 ≤ cmd의 원소 개수 ≤ 1,000
효율성 테스트 케이스 제한 사항
주어진 조건 외 추가 제한사항 없습니다.

링크드리스트를 이용해 구하는 문제 같았는데 자세히 보면 삭제된 행의 위치만 알수있다면 결과값은 구할수있다.

코드(결과값만 필요하다면)

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> stack= new Stack();
        int size = n;
        for(String c:cmd){
            String[] tmp = c.split(" ");
            switch(tmp[0]){
                case "D":
                    k+=Integer.parseInt(tmp[1]);
                    break;
                case "U":
                    k-=Integer.parseInt(tmp[1]);
                    break;
                case "C":
                    stack.add(k);
                    size--;
                    if(size==k) k--;
                    break;
                case "Z":
                    if(stack.pop()<=k) k++;
                    size++;    
            }
           
        }
        StringBuilder sb= new StringBuilder();
        for(int i=0;i<size;i++){
            sb.append("O");
        }
        while(!stack.isEmpty()){
            sb.insert(stack.pop(),"X");
        }
        return sb.toString();
    }
}

코드(링크드리스트를 이용한)

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Node> stack = new Stack();
        Node root= new Node(-1);
        Node cur= root;
        for(int i=0;i<n;i++){
            Node node = new Node(i);
            cur.next=node;
            node.prev=cur;
            cur= node;
        }
        cur.next =new Node(-1);
        cur =root.next;
        for(int i=0;i<k;i++){
            cur= cur.next;
        }
        for(String s:cmd){
            String[] tmp = s.split(" ");
             switch(tmp[0]){
                case "D":
                    int num =Integer.parseInt(tmp[1]);
                    while(num-->0){
                        cur=cur.next;
                    }
                    break;
                case "U":
                     num =Integer.parseInt(tmp[1]);
                    while(num-->0){
                        cur=cur.prev;
                    }
                    break;
                case "C":
                    stack.add(cur);
                    cur.prev.next=cur.next;
                    cur.next.prev=cur.prev;                 
                    cur=cur.next.idx==-1?cur.prev:cur.next;
                    break;
                case "Z":
                     Node tmp1 =stack.pop();
                     tmp1.prev.next=tmp1;
                     tmp1.next.prev=tmp1;
                  
            }
        }
     
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            sb.append("O");
        }
        while(!stack.isEmpty()){
            sb.setCharAt(stack.pop().idx,'X');
        }
        
        return sb.toString();
       
       
    }
    public class Node{
        Node prev,next;
        int idx;
        public Node(int i){
            idx=i;
        }
    }
}

링크드리스트를 이용하는 쪽이 평균적으로 값이 균일하게 나온다.