프로그래머스 [Lv. 3] 표 편집 {언어 : Java} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

import java.util.Stack;
import java.util.Arrays;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> st = new Stack<>();
        int[] upRow = new int[n+2];
        int[] downRow = new int[n+2];
        int[] visited = new int[n];
        
        for (int i = 0; i < n+2; i++) {
            upRow[i] = i - 1;
            downRow[i] = i + 1;
        }
        // 시작지점도 1 올려줘야함
        // 행이 하나 밀렸기 때문
        k += 1;
        
        for (String c : cmd) {
            if (c.length() == 1) {
                if (c.charAt(0) == 'C') {
                    st.push(k);
                    visited[k-1] = 1;
                    // 밑 행의 윗 행은 k가 아니라 k의 윗 행으로 바뀌어야 하므로
                    // 밑 행 = downRow[k]
                    // 밑 행의 윗 행 = upRow[밑 행]
                    // 여기에 현재 k의 윗 행을 넣어준다.
                    upRow[downRow[k]] = upRow[k];
                    
                    // 윗 행의 밑 행은 k가 아니라 k의 밑 행으로 바뀌어야 하므로
                    // 윗 행 = upRow[k]
                    // 윗 행의 밑 행 = downRow[윗 행]
                    // 여기에 현재 k의 밑 행을 넣어준다.
                    downRow[upRow[k]] = downRow[k];
                    
                    // 위치 조정
                    // 삭제 하면 밑 행으로 가야한다.
                    // 하지만 밑 행이 없는 경우 => n + 1인 경우 현재의 윗 행으로
                    if (downRow[k] == n + 1) {
                        k = upRow[k];
                    } else {
                        k = downRow[k];
                    }
                    
                } else {
                    // 원래 행으로 돌아가서
                    int ctrlZ = st.pop();
                    visited[ctrlZ-1] = 0;
                    
                    // 현재 행의 윗 행의 밑 행이 현재 행이 되도록
                    downRow[upRow[ctrlZ]] = ctrlZ;
                    
                    // 현재 행의 밑 행의 윗 행이 현재 행이 되도록
                    upRow[downRow[ctrlZ]] = ctrlZ;
                    
                }
            } else {
                int cnt = Integer.valueOf(c.split(" ")[1]);
                if (c.charAt(0) == 'U') {
                    while (cnt > 0) {
                        cnt--;
                        k = upRow[k];
                    }
                } else {
                    while (cnt > 0) {
                        cnt--;
                        k = downRow[k];
                    }
                }
            }
        }
        
        StringBuilder result = new StringBuilder();
        for (int v : visited) {
            if (v == 1) {
                result.append("X");
            } else {
                result.append("O");
            }
        }
        String answer = result.toString();
        return answer;
    }
}

풀이 방법

• 주석의 내용이 곧 풀이 방법이다.
• 현재 위치를 지웠다고 했을 때
  • upRow는 x 위치의 윗 행을 downRow는 x 위치의 밑 행을 나타낸다.
  • 현재 위치의 윗 행은 upRow[k] 이고 아래 행은 downRow[k]가 된다.
  • 윗 행의 아래 행은 k가 아니라 k의 밑 행인 downRow[k]가 되어야 하고
  • 아래 행의 윗 행은 k가 아니라 k의 윗 행인 upRow[k]가 되어야 한다.
  • 정리하면
    • downRow[upRow[k]] = downRow[k];
    • upRow[downRow[k]] = upRow[k];
  • 그리고 삭제 후에 밑 칸으로 가야하는데 밑 칸이 n + 1이라면 없다는 말이므로
    • k = upRow[k] 위로 올라가준다.
    • 그 외는 k = downRow[k]

느낀점

• 이런 방식을 80분 안에 떠올려야 한다는 것이 말이 안된다...