문제 보기 · Level 3 · 2021 카카오 채용연계형 인턴십 · 정답률 42% · 푼 사람 7,420명 (2026-09-30 기준)1

문제

0 ~ n − 1행인 표에서 k행이 선택되어 있다. 명령은 네 가지다.

  • "U X": X칸 위의 행을 선택한다. "D X": X칸 아래의 행을 선택한다.
  • "C": 선택된 행을 지우고 바로 아래 행을 선택한다. 지운 행이 마지막 행이면 바로 위 행을 선택한다.
  • "Z": 가장 최근에 지운 행을 원래 자리에 되살린다. 선택된 행은 그대로다.

모든 명령을 마친 뒤, 처음 표와 비교해 남아 있는 행은 O, 지워진 행은 X로 적은 문자열을 돌려준다.

  • 5 ≤ n ≤ 1,000,000
  • 명령 최대 200,000개, 모든 X의 합 ≤ 1,000,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 연결 리스트: 행마다 위·아래 이웃만 기억하면 지우기와 되살리기가 한 번에 끝난다.
  • 스택: “가장 최근에 지운 행부터” 되살리니, 지운 행 번호를 쌓아 두고 꺼낸다.
1단계 · 작은 예로 손으로 풀기

5행 표에서 2행이 선택되어 있다. 명령은 C, C, Z다.

  • C: 2행을 지운다. 표는 0, 1, 3, 4행이고, 바로 아래였던 3행이 선택된다.
  • C: 3행을 지운다. 표는 0, 1, 4행이고, 4행이 선택된다.
  • Z: 가장 최근에 지운 3행을 되살린다. 표는 0, 1, 3, 4행이고, 선택은 여전히 4행이다.

결과는 OOXOO다. 되살릴 때 “3행은 원래 1행과 4행 사이에 있었다”를 알아야 한다.

2단계 · 가장 단순한 방법과 그 속도

살아 있는 행 번호를 파이썬 리스트에 두고 pop, insert로 지우고 되살린다. 가운데를 지우면 뒤의 행을 모두 한 칸씩 당기니 한 번에 \(O(n)\)이다. 명령 20만 번 × 행 100만 개면 최악 2,000억 번이라, 정확성 테스트(n ≤ 1,000)는 통과해도 효율성 테스트는 못 넘는다.

3단계 · 핵심 아이디어
  • 행마다 위 이웃 prev와 아래 이웃 nxt를 적는다. 처음에는 i의 위가 i − 1, 아래가 i + 1이다. 위가 없으면 −1, 아래가 없으면 n으로 적는다.
  • C: 위 이웃의 아래를 내 아래로, 아래 이웃의 위를 내 위로 바꾼다. 지워진 행 자신의 prev, nxt는 그대로 둔다. 지운 행 번호는 스택에 쌓는다.
  • Z: 스택에서 꺼낸 행 x는 아직 “내 위는 p, 아래는 q”를 기억한다. p의 아래와 q의 위를 다시 x로 바꾸면 된다. 가장 최근에 지운 행부터 되살리니, p와 q가 지금 표에 살아 있다.
  • U, D: 이웃을 X번 따라간다. X의 합이 100만 이하라 모두 합쳐도 100만 걸음이다.
  • 답: 마지막에 스택에 남은 행이 지워진 행이다.
4단계 · 코드 흐름
  1. prev, nxt 리스트와 빈 스택을 만든다. 선택된 행 cur = k.
  2. 명령마다:
    • U X, D X: prev나 nxt를 X번 따라간다.
    • C: cur를 스택에 넣고, 양옆을 서로 잇는다. 아래 이웃이 있으면 그리로, 없으면 위 이웃으로 cur를 옮긴다.
    • Z: 스택에서 꺼내 양옆이 다시 그 행을 가리키게 한다.
  3. 모두 O로 채운 뒤 스택에 남은 행만 X로 바꾼다.
5단계 · 파이썬 코드 
def solution(n, k, cmd):
    prev = [i - 1 for i in range(n)]
    nxt = [i + 1 for i in range(n)]
    removed = []                              # 지운 행을 쌓는 스택
    cur = k
    for c in cmd:
        if c[0] == "U":
            for _ in range(int(c[2:])):
                cur = prev[cur]
        elif c[0] == "D":
            for _ in range(int(c[2:])):
                cur = nxt[cur]
        elif c[0] == "C":
            removed.append(cur)
            p, q = prev[cur], nxt[cur]
            if p != -1: nxt[p] = q            # 위 이웃 → 내 아래
            if q != n: prev[q] = p            # 아래 이웃 → 내 위
            cur = q if q != n else p          # 마지막 행이면 위로
        else:                                 # Z
            x = removed.pop()
            p, q = prev[x], nxt[x]            # x가 기억하는 이웃
            if p != -1: nxt[p] = x
            if q != n: prev[q] = x
    ans = ["O"] * n
    for x in removed:
        ans[x] = "X"
    return "".join(ans)
  • c[2:]: "U 10"에서 세 번째 글자부터, 곧 "10"이다. c[-1]로 쓰면 두 자리 이상에서 틀린다.
  • cur = q if q != n else p: 아래 이웃이 있으면 q, 없으면 p를 고르는 한 줄 조건식이다.
6단계 · 실행 추적

n = 8, k = 2, cmd = [“D 2”, “C”, “U 3”, “C”, “D 4”, “C”, “U 2”, “Z”, “Z”]

명령 선택된 행 표 상태 지운 행 스택
D 2 4 OOOOOOOO []
C 5 OOOOXOOO [4]
U 3 1 OOOOXOOO [4]
C 2 OXOOXOOO [4, 1]
D 4 7 OXOOXOOO [4, 1]
C 6 OXOOXOOX [4, 1, 7]
U 2 3 OXOOXOOX [4, 1, 7]
Z 3 OXOOXOOO [4, 1]
Z 3 OOOOXOOO [4]

“U 3”은 살아 있는 행만 센다. 5행에서 위로 3, 2, 1행을 거쳐 1행이 된다(4행은 지워져 건너뛴다). 답은 OOOOXOOO다.

7단계 · 복잡도와 흔한 실수

처음 리스트를 만드는 데 \(O(n)\), C·Z는 한 번에 \(O(1)\), U·D는 모두 합쳐 \(O(\text{X의 합})\)이다. 행 100만 개, 명령 20만 개로 재 보니 0.1초가 안 걸렸다.

  • 파이썬 리스트의 pop·insert로 풀어 효율성 테스트에서 시간 초과가 난다.
  • 지운 행의 prev, nxt까지 지워 되살릴 수 없게 만든다.
  • 마지막 행을 지운 뒤 위 행을 선택하는 규칙을 빠뜨린다.
  • Z에서 선택된 행까지 바꾼다. Z는 선택을 바꾸지 않는다.
검증: 문제의 예시 2개를 통과했고, 무작위 명령 3,000묶음에서 “살아 있는 행을 리스트로 들고 문제 그대로 흉내 내는” 다른 풀이와 결과가 같았다. 6단계 표의 각 줄과 큰 입력의 시간도 확인했다 — 13_pg81303_p1.py

  1. 프로그래머스 스쿨, “표 편집” (https://school.programmers.co.kr/learn/courses/30/lessons/81303), 2026-09-30 조회. ↩