[프로그래머스/Java] 81303번 표 편집

프로그래머스 표 편집 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/81303

초기 위치를 기억해야 한다는 집착을 버린 뒤에야 풀 수 있었던 문제.

Z가 '가장 최근에 삭제된 행을 원래대로 복구'하는 것인 만큼,
Stack을 활용해야 하는 문제임은 분명하나, Stack에 어느 정보를 저장해야 하는 지 혼란스러웠다.

결국 삭제된 시점의 위치를 저장하여 해결하였다.

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        
        StringBuilder builder = new StringBuilder();
        int rowNum = n;
        Stack<Integer> deleted = new Stack<>();
        
        for(String tmp : cmd){
            if(tmp.length() > 1){
                int x = Integer.parseInt(tmp.substring(2));
                if(tmp.charAt(0) == 'U') k -= x;
                else k += x;
            } else if (tmp.charAt(0) == 'C'){
                deleted.push(k);
                rowNum--;
                if(rowNum == k) k--;
            } else {
                rowNum++;
                if(deleted.pop() <= k) k++;
            }
        }
        
        for(int i = 0 ; i < rowNum ; i++)
            builder.append("O");
        while(!deleted.empty())
            builder.insert(deleted.pop(), "X");
        
        return builder.toString();
    }
}

.
.
.

다른 분들의 풀이를 보니 Stack과 함께 표를 LinkedList로 구현해 푸는 것이 모범답안인 듯 하다.
이전 노드, 다음 노드 정보를 갖고 있는 Node를 LinkedList로 구현해놓고,
삭제 후 복구할 때도 기억하고 있는 위치 그대로 복구시키는 것이다.

전형적인 알고리즘 문제에 익숙해 질 수록 오히려 기초적인 자료구조를 떠올리기 어려워지는 것 같다.
조금 더 유연하게 사고하기 위해서는 다른 분들의 코드도 많이 읽고, 공부를 게을리 하지 말아야겠다.