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

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

코딩테스트 연습 - 표 편집

밑에 설명과 같은 그림이 들어오면 명령어에 따라 선택된 행 이동, 삭제, 복구 작업을 수행한다.

 

처음에는 효율성 생각 안하고 정확도만 따지기 위해 다음과 같은 방법을 이용했는데,

결론부터 말하면 정확도, 효율성 모두 통과 못한다.

[통과 못한 코드]

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> removed = new Stack<>();
        ArrayList<String> arr = new ArrayList<String>();
        
        for(int i=0; i<n; i++){
            arr.add(Integer.toString(i));
        }
        
        for(String s : cmd){
            char ch = s.charAt(0);
            
            switch(ch){
                    //up : index 작아짐
                case 'U':{
                    int num = s.charAt(2)-'0';
                    for(int i=0; i<num && k>0;i++){
                        if(arr.get(k).equals("-")){
                            i--;
                        }
                        k--;
                    }
                    break;
                }
                    //down : index 커짐
                case 'D':{
                    int num = s.charAt(2)-'0';
                    for(int i=0; i<num && k<arr.size()-1;i++){
                        if(arr.get(k).equals("-")){
                            i--;
                        }
                        k++;
                    }
                    break;
                }
                case 'C':{
                    removed.push(k);
                    arr.set(k, "-");  //del 넣어줌
                    if(k==(arr.size()-1))
                        k--;
                    else
                        k++;
                    break;
                }
                default:{
                    if(removed.size()==0)
                        break;
                    int num = removed.pop();
                    arr.set(num, Integer.toString(num));
                }   
            }
            
        }
        
        for(String s : arr){
            if(s.equals("-"))
                sb.append("X");
            else
                sb.append("O");
        }
        return sb.toString();
    }
}

ArrayList를 사용한 이유는 행을 삭제하면 뒤에 있는 요소들의 index가 한 칸씩 당겨지기 때문이었다.

그리고 stack은 대표적인 LIFO 방식이기 때문에 최근에 삭제된 행을 복구할때 유용할거같아서 사용했다.

그러면 복구할때, 앞뒤 숫자를 찾은 후 복구를 해야하기 때문에

삭제시 "-"와 같이 일종의 null을 나타내는 String을 만들어 넣어준 후, removed에 넣어 저장하였다.

 

근데 이런 방법을 사용하면 정확도는 둘째치고 절대 효율성에서 통과하지 못한다.

행 개수 n <= 1,000,000이고 명령어 개수 200,000이므로 각 명령어당 전체 행 개수를 탐색하게 된다면
효율성을 만족하지 못한다.

출처 : https://technote-mezza.tistory.com/106

위의 방식을 쓰게 되면 O(n^2)의 효율성이 나오게 된다.

 

여러 해결책이 있는데, 그 중 LinkedList에 대한 이해가 제일 높아 LinkedList를 사용하였다.

LinkedList를 사용하게 되면 삽입, 삭제는 O(1) 이고, 이동은 O(x)이기 때문에 훨씬 효율적이다.

https://macinjune.com/all-posts/web-developing/mac-develop-tip/c-doubly-linked-list-%EA%B5%AC%ED%98%84/

Doubly LinkedList를 사용하여 양방향 노드와 Root와 Tail까지 구현하였고,

만약 현재 Node에서 삭제 요청이 오면 prev와 Next의 정보를 가진 현재 Node를 그대로 Removed Stack에 넣어주고

현재 Node의 앞 뒤를 연결하면 된다! 

반대로 최근에 삭제된 Node를 복구하는 요청이 오면 Stack에서 꺼낸 후, 

복구할 Node의 prevNode의 next와 Nextnode의 prev부분에 복구할 Node를 넣어주면 다시 연결된다!

 

이 방식으로 코드를 작성하면 된다. 문제 해결한 코드는 올려도 되는지 잘 모르겠다.. 일단 지웠다.!

카카오 코딩테스트는 블로그에 문제 해설도 많이 있기 때문에 참조하면 좋을 듯 하다..!

https://tech.kakao.com/?s=%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8 

Search for "코딩테스트"

[참조]

https://settembre.tistory.com/480