[프로그래머스 2021 카카오 채용연계형 인턴십] 표 편집 - JAVA(자바)

문제 링크

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

프로그래머스

해설

문제 조건을 보면 행의 개수 n의 범위가 5 ≤ n ≤ 1,000,000 이고 명령어들이 담긴 배열 cmd의 범위는 1 ≤ cmd ≤ 200,000 이 된다.

 

모든 행에 대해서 삽입, 삭제를 배열에서 하면 O(n*cmd) 이 돼서 시간 초과가 된다. 그래서 처음 생각은 삽입, 삭제에 유리한 LinkedList를 고려했지만 삽입,삭제가 O(1) 이지 그 노드까지 가려면 O(n)이 걸린다. (참고로 Java에서 LinkedList 는 투 포인터로 노드 탐색을 한다) 그래서 배열, LinkedList 두 자료구조를 사용해야 하나? 하는 생각을 했는데 어쨌든 두 자료구조를 동기화해서 풀려면 O(n) 시간이 소요되는 걸 피할 수 없다.

 

그래서 해설을 찾아보니 이런 자료구조를 사용해서 상태를 보관할 필요 없이 n,k 변수와 삽입, 삭제 되는 행의 번호를 기록하는 Stack 자료만 사용하면 됐다. 각 cmd에 대해 로직은 문제에서 요구하는데로만 풀린다. 단, 마지막에 문자를 출력할 때 stack에 남아 있는 번호들은 복구하지 않은 행이므로 그 행 번호에 문자 "X" 만 추가하면 문제가 풀린다.

코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmds) {
        Stack<Integer> stack = new Stack<>();  // 삭제된 행 번호
        for(String cmd : cmds){
            char c = cmd.charAt(0);
            if(c == 'U'){
                k -= Integer.parseInt(cmd.substring(2));
            }else if(c == 'D'){
                k += Integer.parseInt(cmd.substring(2));
            }else if(c == 'C'){
                if(stack.push(k) == n - 1){ // 현재 위치가 바닥에 있는 경우
                    k--;
                }
                n--;
            }else if(c == 'Z'){
                n++;
                if(stack.pop() <= k){ // 현재 위치 위에 복구되는 경우 현재 선택된 행 번호가 바꾼다.
                    k++;   
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append("O");
        }
        while(!stack.isEmpty()){
            sb.insert(stack.pop().intValue(), "X");
        }
        
        return sb.toString();
    }
}