표 편집

2025-10-12

#JAVA#프로그래머스

4분

문제 링크

문제 풀이 시간 : 1시간 14분

문제 요약

•
0 ~ n-1 행으로 이루어진 표가 있고, 처음 선택된 행은 k

•
명령어 목록 cmd가 주어지며 한 번에 한 행만 선택됨, 표 범위를 벗어나는 이동은 주어지지 않음

•
지원 명령:
- ◦
  U X: 현재 선택 행에서 위로 X칸(삭제된 행은 건너뜀)
- ◦
  D X: 현재 선택 행에서 아래로 X칸(삭제된 행은 건너뜀)
- ◦
  C: 현재 선택 행 삭제, 기본은 바로 아래 행을 선택 (아래가 없으면 위 행)
- ◦
  Z: 가장 최근에 삭제한 행 복구, 현재 선택 행은 변하지 않음

•
모든 명령 수행 후, 처음 표(0 ~ n-1) 기준으로 삭제되지 않은 행은 O, 삭제된 행은 X 로 표시한 문자열을 반환

문제 풀이

이 문제를 보고 처음 생각난 풀이 방법은 그냥 배열을 이용해서 푸는 방법이었다.

만약 n이 4라면 길이가 4인 정수 배열을 만들고 각 인덱스에 자기 자신을 넣어 두는 것이다.

그리고 삭제되면 해당 인덱스는 -1로 설정하여 삭제된 것을 표기하는 방식으로 풀려고 했다.

예를 들어, n=4라면

Java

arr = [0, 1, 2, 3]

과 같이 초기화 하고,

삭제된 행은 arr[i] = -1로 바꾸는 방식이다.

그래서 나온 방식이 아래 코드와 같다.

초기 코드

삭제 후 다음 선택된 행 찾기

Java

public int last(int k){
				//일단 삭제한 행 밑으로 이동함
        for(int i=k+1;i<n;i++){
            if(arr[i]!=-1)
                return i;
        }
        //삭제한 행 밑에 남아있는 행이 없다면 위로 이동하며 처음으로 나오는 행 찾아서 반환
        for(int i=k-1;i>=0;i--){
            if(arr[i]!=-1)
                return i;
        }
        return 0;
    }

위, 아래로 이동

Java

public int move(int k, int num, int dir){
				//dir이 -1인 경우 위로, 1인 경우 아래로 이동
        for(int i=k+dir;i>=0 && i<n;i+=dir){
	        // 이미 삭제된 행이면 뛰어넘음
            if(arr[i]==-1){
                continue;
            }
            num--;
            if(num==0)
                return i;
        }
        return k;
    }

Java

import java.util.*;

class Solution {
    public int[] arr;
    public int n;
    
    public int last(int k){
        for(int i=k+1;i<n;i++){
            if(arr[i]!=-1)
                return i;
        }
        for(int i=k-1;i>=0;i--){
            if(arr[i]!=-1)
                return i;
        }
        return 0;
    }
    
    public int move(int k, int num, int dir){
        for(int i=k+dir;i>=0 && i<n;i+=dir){
            if(arr[i]==-1){
                continue;
            }
            num--;
            if(num==0)
                return i;
        }
        return k;
    }
    
    public String solution(int n, int k, String[] cmd) {
        arr = new int[n];
        this.n = n;
        for(int i=0;i<n;i++)
            arr[i] = i;
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        for(int i=0;i<cmd.length;i++){
            int num;
            switch(cmd[i].charAt(0)){
		            //위로 이동
                case 'U':
                    num = Integer.parseInt(cmd[i].substring(2).trim());
                    k = move(k, num, -1);
                    break;
                //아래로 이동
                case 'D':
                    num = Integer.parseInt(cmd[i].substring(2).trim());
                    k = move(k, num, 1);
                    break;
                //삭제 후 다음 행으로 이동
                case 'C':
                    arr[k] = -1;
                    stack.push(k);
                    k = last(k);
                    break;
                //최근 삭제된 행 복구
                case 'Z':
                    int redo = stack.pop();
                    arr[redo] = redo;
                    break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(arr[i]!=-1)
                sb.append("O");
            else
                sb.append("X");
        }
        
        return sb.toString();
    }
}

/*
리스트로 0~n-1까지 넣어두기
idx 변수로 현재 선택된 행 번호 저장
특정 행 삭제하면 리스트에 -1로 표기, 스택에 쌓기
*/

이 코드도 제대로 동작은 하고 정확성 테스트는 무사히 통과했지만, 효율성 테스트에서 시간초과가 나게된다.

왜냐하면 move()나 last()에서 매번 전체 배열을 선형 탐색하기 때문이다. 삭제된 행이 많아지면 이동할 때마다 거의 모든 행을 확인해야 하는 상황이 생긴다.

개선 방향

이 문제는 사실 이중 연결 리스트 형태로 풀어야 하는 문제였다.

각 행이 이전 행(prev)와 다음 행(next)에 대한 정보를 알고 있다면 삭제 및 복구 연산을 $O(1)$ 로 처리할 수 있기 때문이다.

이중 연결 리스트 초기화

Java

for (int i = 0; i < n; i++) {
    prev[i] = i - 1;                 // i행의 위쪽은 i-1
    next[i] = (i == n - 1) ? -1 : i + 1; // i행의 아래쪽은 i+1 (마지막 행은 -1)
}

삭제

Java

stack.push(new Del(k, prev[k], next[k])); // 삭제 정보 저장

// 삭제된 행을 리스트에서 제거
if (prev[k] != -1) next[prev[k]] = next[k];
if (next[k] != -1) prev[next[k]] = prev[k];

// 다음 선택 행 결정 (아래가 있으면 아래, 없으면 위)
k = (next[k] != -1) ? next[k] : prev[k];

복구

Java

Del redo = stack.pop();

// 복구된 행의 위/아래 행과 다시 연결
if (redo.prev != -1) next[redo.prev] = redo.num;
if (redo.next != -1) prev[redo.next] = redo.num;

// 복구된 행 자신의 연결 정보도 되살림
prev[redo.num] = redo.prev;
next[redo.num] = redo.next;

최종 코드

Java

import java.util.*;

class Solution {
    public class Del{
        public int num;
        public int prev;
        public int next;
        
        public Del(int num, int prev,int next){
            this.num = num;
            this.prev = prev;
            this.next = next;
        }
    }
    
    public String solution(int n, int k, String[] cmd) {
        int[] prev = new int[n];
        int[] next = new int[n];
        Deque<Del> stack = new ArrayDeque<>();
        
        for(int i=0;i<n;i++){
            prev[i] = i-1;
            next[i] = i == n-1 ? -1 : i+1;
        }
        
        for(String now : cmd){
            char op = now.charAt(0);
            if(op == 'U' || op == 'D'){
                int move = Integer.parseInt(now.substring(2).trim());
                
                if(op == 'U'){
                    for(;move>0;move--){
                        k = prev[k];
                    }
                } else{
                    for(;move>0;move--){
                        k = next[k];
                    }
                }
            }
            else if(op=='C'){
                stack.push(new Del(k,prev[k], next[k]));
                
                if(prev[k]!=-1)
                    next[prev[k]] = next[k];
                if(next[k]!=-1)
                    prev[next[k]] = prev[k];
                
                k = next[k]==-1 ? prev[k] : next[k];
            }
            else if(op=='Z'){
                Del redo = stack.pop();
                
                if(redo.prev!=-1)
                    next[redo.prev] = redo.num;
                if(redo.next!=-1)
                    prev[redo.next] = redo.num;
                
                prev[redo.num] = redo.prev;
                next[redo.num] = redo.next;
            }
        }
        
        char[] ans = new char[n];
        Arrays.fill(ans, 'O');
        for(Del now : stack){
            ans[now.num] = 'X';
        }
        return new String(ans);
    }
}