표 편집(프로그래머스) JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

문제 설명

• "D 2"를 실행한 뒤 "C"를 실행할 경우

• "U 3"을 실행한 뒤 "C"를 실행할 경우

• "D 4"를 수행한 다음 "C"를 실행할 경우

• "U 2"를 실행할 경우

• "Z"를 실행할 경우

• "Z"를 실행할 경우

결과는 처음과 비교해서 없어진 것은 X표시로 처리한다.

 

문제에 대한 아이디어 및 구현

제일 처음 문제를 풀 때는 HashMap을 이용해 풀었다. 하지만 위치인 k를 변경하는데에서 마음대로 진행이 되지 않았다. 

접근법이 틀린 것 같아 구글링을 해본 결과 바킹독님이 푼 풀이를 볼 수 있었다.

 

https://blog.encrypted.gg/1001?category=916869 

[2021 카카오 채용연계형 인턴십] Q3. 표 편집 (C++, Python, Java)

이 내용을 참고해서 풀었다.

 

연결 리스트를 이용해서 풀기

커서가 돌아다니면 중간에 내용을 삭제하므로 연결 리스트가 필요한 문제임을 유츄할 수 있다.

연결리스트가 가지고 있는 내용은 3가지이다. 전 노드의 index, 현재 index, 다음 index 이렇게 3가지 내용을 가지고 있다.

이런 형식으로 사용된다. 하지만 이 코드에서는 직접적으로 연결리스트를 사용하지 않는다. pre 배열과 next 배열을 이용해 연결 리스트를 구현한다.

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;

• U 명령어 처리

위로 올라가는 명령어는 간단하게 처리할 수 있다. 입력받는 수만큼 pre로 이동하면 된다.

if(type == 'U'){
     int num = Integer.parseInt(cmd[i].substring(2));
     while(num-- > 0){
           k = pre[k];
        }
 }

• D 명령어 처리

else if(type == 'D'){
    int num = Integer.parseInt(cmd[i].substring(2));
    while(num-- > 0){
          k = next[k];
    }
}

• C 명령어 처리 삭제

삭제는 연결 리스트에서 삭제 하는 방법을 그대로 이용하면 된다.

현재 인덱스를 기준으로 다음 인데스의 pre와 전 index의 next를 연결한다. 그러면 현재 인덱스는 삭제 된다.

else if(type == 'C'){
     dq.addFirst(new Node(pre[k],k,next[k]));
     if(pre[k] != -1) next[pre[k]] = next[k]; //전 인덱스의 next를 다음 인데스로 변경
     if(next[k] != -1) pre[next[k]] = pre[k]; //다음 인덱스의 pre를 전 인덱스로 변경
     sb.setCharAt(k, 'X');
     if(next[k] != -1) k = next[k];
     else k = pre[k];
}

• Z 명령어 처리 되돌리기

이 부분을 수행하기 위해서는 제일 최근에 삭제한 노드를 가지고 있어야 한다. 그래서 위에 코드에 있는 것처럼 Deque를 통해 제일 최근에 삭제한 노드를 가지고 있다. 제일 최근에 삭제한 노드를 꺼낸 뒤 원래 있던 위치에 넣어주면 된다. 이 되돌리기 명령어를 처리하기 위해 직접적으로 연결리스트를 만들지 않고 pre와 next 배열 2개를 이용한 것이다.

배열은 노드가 가리키는 곳에 바로 접근이 가능하기 때문이다!!

 else{
     Node node = dq.removeFirst();
     if(node.pre != -1) next[node.pre] = node.cur;
     if(node.nxt != -1) pre[node.nxt] = node.cur;
     sb.setCharAt(node.cur, 'O');
}

 

전체 코드

import java.util.*;

class Solution {
    public class Node{
        int pre, cur, nxt;
        public Node(int pre, int cur, int nxt){
            this.pre = pre;
            this.cur = cur;
            this.nxt = nxt;
        }
    }
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        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;
        
        Deque<Node> dq = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder("O".repeat(n));
        for(int i = 0; i<cmd.length; ++i){
            char type = cmd[i].charAt(0);
            if(type == 'U'){
                int num = Integer.parseInt(cmd[i].substring(2));
                while(num-- > 0){
                    k = pre[k];
                }
            }
            else if(type == 'D'){
                 int num = Integer.parseInt(cmd[i].substring(2));
                while(num-- > 0){
                    k = next[k];
                }
            }
            else if(type == 'C'){
                dq.addFirst(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{
                Node node = dq.removeFirst();
                if(node.pre != -1) next[node.pre] = node.cur;
                if(node.nxt != -1) pre[node.nxt] = node.cur;
                sb.setCharAt(node.cur, 'O');
            }
        }
       
        return answer = sb.toString();
    }
}