[프로그래머스]표 편집 - JAVA

** 풀이가 추가되었습니다. 추가된 풀이가 정확한 풀이입니다. **

---

[프로그래머스]표 편집

코딩테스트 연습 - 표 편집

풀이

🪑 올해 카카오 인턴십 코딩테스트 문제이다.

StringBuilder때문에 한참 헤메였던 문제.. StringBuilder 사용을 잘 안해보다보니 append외엔 함수를 몰랐었다. insert라는 함수가 있다는 것을 알게 되기까지 너무 오래걸렸당..ㅜ

 

** 추가 **

위의 방식으로 StringBuilder의 insert함수를 사용해도 현재 문제는 통과를 할 수 있었으나, 댓글 달아주신 '바킹독'님의 설명에 따라 효율성 부분에서 통과하기 어려운 풀이였습니다. 정확한 풀이가 아님을 알 수 있었고, 연결리스트 방식을 활용하여 푸는것이 정확한 풀이입니다.

 

 

먼저 문제를 정리해 보자!

• 명령어를 사용하며 한 번에 선택 가능한 행은 하나이다.
• 명령어의 종류는 총 4가지로 'U, D, C, Z'가 있다.
• 명령어를 수행한 후 변경된 표에서 다시 행을 선택한다.
• 모든 명령어가 실행된 후 삭제된 행의 여부에 따라 'O'또는 'X'의 문자열을 만들어 반환한다.

 

* 원래 풀이

 

🔧 이제 문제 풀이 과정을 생각해보자.

1. 명령어를 실행한다.
2. 삭제되지 않은 행은 'O', 삭제된 행은 'X'로 표시하여 문자열로 만들어준다.

 

🔹 명령어를 실행한다.

입력받는 명령어의 종류에 따른 연산을 진행한다.

• "U X": 현재 행 위치에서 X만큼 빼준다.
• "D X": 현재 행 위치에서 X만큼 더해준다.
• "C": 스택에 현재 행 정보를 담고, 테이블 크기를 줄여준다. 만약, 삭제된 행이 마지막 행이라면 현재 행 위치에서 하나를 빼준다.
• "Z": 스택에서 가장 최근에 삭제된 행의 정보를 가져온다. 만약, 행이 현재 행보다 위에 추가되는 행이라면 현재 행의 위치를 하나 더해준다. 테이블의 크기를 키워준다.

 

🔹 삭제되지 않은 행은 'O', 삭제된 행은 'X'로 표시하여 문자열로 만들어준다.

- StringBuilder를 사용한다.

- 현재 테이블의 크기만큼은 행이 삭제되지 않은 것이므로 'O'를 append 해준다.

- 스텍에서 삭제된 행을 순서대로 꺼내며 위치를 복구해주고, 해당 위치에는 'X'를 insert 해준다.

 

 

** 연결리스트를 활용한 풀이 **

 

🔹 pre, next배열을 사용한다.

• 각각의 인덱스에 해당하는 위치의 이전 노드, 다음 노드의 위치를 기억한다.
• 맨 첫 번째 노드의 이전 노드와 맨 마지막 노드의 다음 노드는 -1로 설정해 준다.

 

 

🔹 StringBuilder를 사용하여 n크기 만큼의 'O' 문자열을 만들어 준다.

• 전체 표의 길이에 해당하는 문자열을 미리 만들어 둔다.

 

 

🔹 LinkedList방식을 활용하여 이전, 다음 노드의 위치를 기억하는 배열을 만들어 준다.

• 삽입, 삭제 시에만 이전노드와 다음노드를 변경시켜주는 작업을 진행하면 된다.

 

 

🔹 삭제 연산을 수행한다.

• 삭제시 스택에 현재노드, 현재노드의 이전노드, 현재노드의 다음노드를 넣어 주고 현재 노드가 삭제되었다고 생각하여 이전 노드의 다음 노드를 현재 노드의 다음노드로 연결해 준다. 마찬가지로 다음 노드의 이전 노드를 현재 노드의 이전노드로 연결해 준다.
• 삭제된 위치는 'X'문자로 변경해 준다.
• 삭제 후 바로 다음 노드를 선택해야 하는데 다음 노드의 값이 -1이라면 현재 선택된 행이 마지막 행이라는 의미이므로 현재 행을 선택한다.

 

 

🔹 복구 연산을 수행한다.

• 스택에서 가장 최근 삭제된 노드부터 하나씩 꺼내준다.
• 삭제할 때의 이전노드, 현재노드, 다음노드의 정보를 적절히 활용해 준다.
• 삭제할 때의 이전노드가 -1이 아니라면(첫 번째 노드가 아니라면) 이전 노드와의 연결 정보를 복구해 준다.
• 마찬가지로 삭제할 때의 다음 노드가 -1이 아니라면(마지막 노드가 아니라면) 다음 노드와의 연결 정보를 복구해 준다.
• 복구된 위치는 'O'문자로 변경해 준다.

 

 

코드

** 추가된 풀이**  연결리스트를 활용한 풀이 - 시간복잡도O(n + 1000000)

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 c = cmd[i].charAt(0);
            if(c == 'U') {
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num-- > 0) {
                    k = pre[k];
                }
            } else if(c == 'D') {
                int num = Integer.valueOf(cmd[i].substring(2));
                while(num-- > 0) {
                    k = next[k];
                }
            } else if(c == '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 {
                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();
    }
    
    public class Node{
        int pre, cur, nxt;
        
        public Node(int pre, int cur, int nxt) {
            this.pre = pre;
            this.cur = cur;
            this.nxt = nxt;
        }
    }
}

 

 

* StringBuilder의 insert함수를 활용한 풀이 - 시간복잡도O(n^2)

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

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