[프로그래머스/Java] Lv.3 - 표 편집

승래·2026년 3월 19일

linkedlist 자바 프로그래머스

프로그래머스 Lv.3 - 표 편집

요구사항

n개의 행이 있는 표에서 명령어(U, D, C, Z)를 수행한 후
삭제된 행은 X, 남은 행은 O로 출력하는 문제

접근 방식

처음에 ArrayList로 구현했으나 효율성 테스트 실패.
→ 배열로 LinkedList를 직접 구현해서 해결했다.

ArrayList 방식이 시간초과인 이유

remove(index), add(index, value) 가 O(n)
cmd가 최대 200,000개 → 전체 O(n²) → 시간초과

배열 LinkedList 방식

int[] prev = new int[n+2];  // 이전 행 인덱스
int[] next = new int[n+2];  // 다음 행 인덱스

삭제/복구가 모두 O(1)!

핵심 아이디어: 삭제해도 노드의 prev, next 값을 유지

삭제 전: ... ↔ 2 ↔ [3] ↔ 4 ↔ ...

C (삭제):
next[prev[3]] = next[3]  → 2의 다음을 4로
prev[next[3]] = prev[3]  → 4의 이전을 2로
결과: ... ↔ 2 ↔ 4 ↔ ...
(3은 연결에서 제외되지만 prev[3]=2, next[3]=4는 유지!)

Z (복구):
next[prev[3]] = 3  → 2의 다음을 다시 3으로
prev[next[3]] = 3  → 4의 이전을 다시 3으로
결과: ... ↔ 2 ↔ 3 ↔ 4 ↔ ...

경계값 처리

1-indexed 사용 (0: 가상 헤드, n+1: 가상 테일)
next[0] = 1, prev[n+1] = n
삭제 후 이동: nextNow == n+1이면 위로, 아니면 아래로

코드

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        StringBuilder answer = new StringBuilder();

        int[] prev = new int[n+2];
        int[] next = new int[n+2];

        for (int i = 1; i <= n; i++) {
            prev[i] = i-1;
            next[i] = i+1;
        }
        next[0] = 1;
        prev[n+1] = n;

        int now = k+1;
        Stack<Integer> stack = new Stack<>();

        for (String line : cmd) {
            StringTokenizer st = new StringTokenizer(line);
            String token = st.nextToken();

            if (token.equals("D")) {
                int num = Integer.parseInt(st.nextToken());
                for (int i = 0; i < num; i++) now = next[now];
            }
            else if (token.equals("U")) {
                int num = Integer.parseInt(st.nextToken());
                for (int i = 0; i < num; i++) now = prev[now];
            }
            else if (token.equals("C")) {
                stack.push(now);
                int prevNow = prev[now];
                int nextNow = next[now];
                next[prevNow] = nextNow;
                prev[nextNow] = prevNow;
                now = (nextNow == n+1) ? prevNow : nextNow;
            }
            else {
                int num = stack.pop();
                next[prev[num]] = num;
                prev[next[num]] = num;
            }
        }

        boolean[] check = new boolean[n+1];
        while (!stack.isEmpty()) check[stack.pop()] = true;

        for (int i = 1; i <= n; i++) {
            answer.append(check[i] ? "X" : "O");
        }

        return answer.toString();
    }
}