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

🖇️ 문제 링크

코딩테스트 연습 - 표 편집

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다 위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행 을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다.

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

 

---

📝 문제 분석

최대 100만개의 원소가 있고, 최대 20만번의 명령을 수행해야 합니다.

삭제 명령이 있기 때문에 배열을 사용하게 된다면 시간 내에 수행할 수 없습니다.

양방향 연결리스트를 구현하여 원소 삭제와 원소 복원 명령 수행시간을 최소화합니다.

가장 최근에 삭제한 원소를 복구시키기 위해, 삭제 했던 원소를 스택에 저장시켜놓습니다. 복구할 때는, 삭제한 원소의 원래 prev 노드와 next노드의 중간에 연결시켜줍니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Node[] nodeArr = new Node[1000000];
        
        for(int i = 0; i < n; i++)
            nodeArr[i] = new Node();
        
        for(int i = 1; i < n; i++) {
            nodeArr[i - 1].next = nodeArr[i];
            nodeArr[i].prev = nodeArr[i - 1];
        }
        
        Deque<Node> stk = new ArrayDeque<>();
       	Node curr = nodeArr[k];
        
        for(String str : cmd) {
        	char c = str.charAt(0);
            switch(c) {
                case 'U' :
                    int x = Integer.parseInt(str.substring(2));
                    for(int i = 0; i < x; i++)
                        curr = curr.prev;
                    break;
                case 'D' :
                    x = Integer.parseInt(str.substring(2));
                    for(int i = 0; i < x; i++)
                        curr = curr.next;
                    break;
                case 'C' :
                    curr.removed = true;
                    stk.push(curr);
                    Node up = curr.prev;
                    Node down = curr.next;
                   	
                    if(up != null)
                        up.next = down;
                    
                    if(down != null) {
                        down.prev = up;
                        curr = down;
                    } else {
                        curr = up;
                    }
                    break;
                case 'Z' :
                   	Node recover = stk.pop();
                   	up = recover.prev;
                    down = recover.next;
                    
                    recover.removed = false;
                    if(up != null) {
                        up.next = recover;
                    }
                    
                    if(down != null) {
                        down.prev = recover;
                    }
                    break;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            if(nodeArr[i].removed)
                sb.append("X");
            else
                sb.append("O");
        }
        
        return sb.toString();
    }
    
    class Node {
        boolean removed;
        Node prev;
        Node next;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0