[프로그래머스] 표 편집 (java)

코딩테스트 연습 - 표 편집 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 표 편집

어떻게 생각하고 문제를 풀었는가?

문제를 보고 먼저 떠올린 것은 LinkedList입니다.

현재 위치를 Iterator로서 표현하고, 노드와 연결된 노드를 x번 탐색하기만 하면 해결되며, 노드의 연결관계를 변경하기만 하면 삭제와 복구가 해결되므로 문제를 해결할 수 있을 것이라고 생각하였습니다.

코드

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Col> stack = new Stack<>();
        Col root = new Col(0);
        Col prev = root;
        Col iter = root;
        for(int i=1; i<n; i++){
            Col col = new Col(i);
            prev.next = col;
            col.prev = prev;
            prev = col;
            if(i==k) iter = col;
        }
        for(String query : cmd){
            char key = query.charAt(0);
            switch(key){
                case 'U':
                    {
                    int x = Integer.valueOf(query.substring(2));
                    while((x--)>0){
                        iter = iter.prev;
                    }
                    break;
                }
                case 'D':{
                    int x = Integer.valueOf(query.substring(2));
                    while((x--)>0){
                        iter = iter.next;
                    }
                    break;
                }
                case 'C':{
                    stack.push(iter);
                    iter = iter.delete();
                    break;
                }
                case 'Z':{
                    stack.pop().restore();
                    break;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append('O');
        }
        while(!stack.isEmpty()) {
            Col col = stack.pop();
            sb.setCharAt(col.value,'X');
        }
        return sb.toString();
    }
    class Col{
        Col prev=null;
        Col next=null;
        int value;
        Col(int index){
            this.value = index;
        }
        void restore(){
            if(this.prev!=null) this.prev.next = this;
            if(this.next!=null) this.next.prev = this;
        }
        Col delete(){
            Col next = this.next;
            Col prev = this.prev;
            if(prev!=null){
                prev.next = this.next;
            }
            if(next!=null){
                next.prev = this.prev;
                return this.next;
            }
            return this.prev;
        }
    }
}

DoubleLinkedList를 직접 구현한 코드입니다.

노드의 앞/뒤로 연결된 노드를 멤버변수로 두어 삭제되었던 노드만으로 복구가 이루어질 수 있도록 클래스를 직접 구현하였습니다.

삭제된 노드는 Stack에 저장되었다가, 복구시 Stack에서 꺼내며, 결과적으로 삭제한 노드의 정보는 Stack에 모두 저장되어 있으므로 Stack의 노드들이 갖는 본래 위치의 문자를 X로 변경하여 문제를 해결합니다.

개선

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> stack = new Stack<>();
        int size = n;
        for(String query : cmd){
            char key = query.charAt(0);
            switch(key){
                case 'U':
                    k-= Integer.valueOf(query.substring(2));
                    break;
                case 'D':
                    k+= Integer.valueOf(query.substring(2));
                    break;
                case 'C':
                    stack.push(k);
                    size--;
                    if(k==size) k--;
                    break;
                case 'Z':
                    int val = stack.pop();
                    if(val<=k) k++;
                    size++;
                    break;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < size; i++) {
            sb.append('O');
        }
        while(!stack.isEmpty()) {
            sb.insert(stack.pop().intValue(), 'X');
        }
        return sb.toString();
    }
}

LinkedList 클래스를 직접 구현하여 문제를 해결하였지만 결과적으로 결과 값을 반환할 때는 Stack에 있는 정보만을 사용하였습니다.

데이터의 삭제를 역순으로 수행한다면 초기의 데이터를 얻을 수 있습니다.

남은 데이터의 수만큼 O문자를 문자열에 추가한 후, 삭제된 index에 X문자를 삽입함으로써 LinkedList를 구현하지 않고 문제를 해결할 수 있습니다.