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

문제

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

프로그래머스

 

알고리즘

스택, 구현

 

 

접근

추가와 삭제가 빈번 -> linked List 이용

결과 : 정확성 통과, 효용성 all 시간초과

 

why?

요소의 개수는 최대 1000,000(백만 개)이고 cmd 연산은 최대 200,000(이십 만)개 임.

 

Linked List로 add 하는 경우

- 내부적으로 포인터 사용하니깐, 해당 인덱스에 있는 요소의 포인터를 새로 추가한 요소에 잇고, 새로 추가한 요소 포인터도 다음을 가리키도 하면 끝이지 않나? 그럼 O(1)

 

remove 하는 경우

- 마찬가지로 내부 포인터 연결 끊어주고 이어주면 끝? 그럼 O(1)  

여기를 잘못 알고 있었음!!

 

삭제는 O(1)이 맞다. 하지만 삭제할 요소를 찾는 것이 O(n)이다. Linked List를 한 줄로 이어진 자료구조로 생각해서 바로 배열처럼 메모리 공간을 찾는 줄 알았는데, 실제로 메모리를 일렬로 저장되어 있지 않기 때문에 연결될 노드들을 항상 따라가야한다.

 

 

stack을 이용하지만 Push, Pop 연산만 함. 그럼 얘도 O(1)

객체 생성 비용과 이용 비용이 있지만 시간초과가 날 정도인가? 그럼 이런 문제는 더 효용성을 따져야 하는건데 기준을 모르겠네. 

 

=> 아님. 내가 푼 알고리즘은 최종적으로 O(n^2)이었음. 

 

 

🪀 실제 배열에 연산을 하는 대신, 인덱스만으로 연산하기

옳은 풀이법을 찾아봤다.

 

linked List의 핵심 데이터인 next, prev 만 따로 관리하는 방법이다. 문제에서 반환해야하는 것은 각 행이 삭제 되었는지 여부이다. 그래서 실제 배열을 선언하고 삽입과 삭제 연산을 하는 것이 아니라, 인덱스만으로 연산을 한다. 

 

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        
         // 리스트에 요소 넣기
        int [] up = new int[n+2];
        int [] down = new int[n+2];

        for(int i=0; i<n+2; i++){
            up[i] = i+1;
            down[i] = i-1;
        }
        k++;

        // 삭제 원소 관리할 스택
        Stack<Integer> stack = new Stack();

        for(String c : cmd){
            String [] str = c.split(" ");
            char ch = str[0].charAt(0);

            if(ch == 'D'){
                int x = Integer.parseInt(str[1]);
                for(int i=0; i<x; i++){
                    k = up[k];
                }
            }
            else if(ch == 'U'){
                int x = Integer.parseInt(str[1]);
                for(int i=0; i<x; i++){
                    k = down[k];
                }
            }
            // 삭제
            else if(ch == 'C'){
                stack.add(k);

                // stack에 정보 넣음
                up[down[k]] = up[k];
                down[up[k]] = down[k];

                if(n < up[k]){
                    k = down[k];
                } else {
                    k = up[k];
                }
            }
            // 복구
            else if(ch == 'Z'){
                int cur = stack.pop();
                up[down[cur]] = cur;
                down[up[cur]] = cur;
            }
        }

        char [] answer = new char[n];
        Arrays.fill(answer, 'O');

        for(int i: stack) {
            answer[i-1] = 'X';
        }
        return new String(answer);
    }
}

 

U\D 연산

- 단순히 인덱스를 증가시키면 안되고, 타고 타고 들어가면서 접근해야한다.

 

삭제 연산

- 복구할 스택에 k(현재 선택된 행)를 추가하여, 복구 작업 때 이용하도록 한다.

- k가 제거 되니, k의 down, up 이 서로를 가리키도록 업데이트 한다.

- 이때, k가 가장 마지막 노드일 때는 k는 down 노드를 가리킨다(문제 그대로)

 

복구 연산

- stack에서 가장 최근에 삭제한 행을 뽑는다.

- k를 다시 이어줘야 하니, k의 up, down 이 k를 가리키도록 업데이트 한다. 

 

출력

- 스택에 남아있으면, 제거 된 행이니 'x' 표시한다.

 

 

새롭게 배운 점

linked List를 실제 데이터 삽입, 삭제 없이 up, down 배열을 통해서만 관리할 수 있구나를 알게됐다. 이 문제 처럼 무슨 데이터가 들어있는지 보여줄 필요가 없을 때는 이렇게 인덱스만 가지고 연산하면 훨씬 빠르구나.