문제 보기 · Level 3 · 2020 KAKAO BLIND RECRUITMENT · 정답률 37% · 푼 사람 7,243명 (2026-09-30 기준)1
문제
n×n 벽면에 기둥(위로 길이 1)과 보(오른쪽으로 길이 1)를 설치하거나 삭제하는 명령이 순서대로 주어진다. 명령은 [x, y, 종류(0 기둥, 1 보), 동작(0 삭제, 1 설치)]다.
- 기둥은 바닥, 보의 한쪽 끝, 다른 기둥 위에만 설 수 있다.
- 보는 한쪽 끝이 기둥 위에 있거나, 양 끝이 다른 보와 이어져 있어야 한다.
수행하면 남은 구조물이 규칙을 어기게 되는 명령은 무시한다. 최종 구조물을 [x, y, 종류] 목록으로, x 오름차순, 같으면 y 오름차순, 그것도 같으면 기둥 먼저 돌려준다.
- 5 ≤ n ≤ 100
- 명령 최대 1,000개
풀이
막히면 한 단계씩 펼친다.
필요한 개념
구현과 시뮬레이션: 규칙을 “이 구조물이 지금 서 있을 수 있나”라는 함수 하나로 옮기고, 명령마다 해 본 뒤 규칙을 어기면 되돌린다. 구조물은 집합에 (x, y, 종류)로 담는다.
1단계 · 작은 예로 손으로 풀기
좌표 (x, y)는 격자선이 만나는 점이다. 기둥 (x, y, 0)은 (x, y)에서 (x, y + 1)까지, 보 (x, y, 1)은 (x, y)에서 (x + 1, y)까지다.
규칙을 좌표로 옮긴다.
- 기둥 (x, y)가 서려면: 바닥(y = 0)이거나, 아래에 기둥 (x, y − 1)이 있거나, 보의 끝 위다. 보의 끝은 왼쪽으로 뻗은 보 (x − 1, y)의 오른쪽 끝, 또는 오른쪽으로 뻗은 보 (x, y)의 왼쪽 끝이다.
- 보 (x, y)가 걸리려면: 왼쪽 끝 아래에 기둥 (x, y − 1)이 있거나, 오른쪽 끝 아래에 기둥 (x + 1, y − 1)이 있거나, 양옆에 보 (x − 1, y)와 (x + 1, y)가 모두 있다.
예: 기둥 (1, 0)을 세우고 보 (1, 1)을 걸면, 보의 왼쪽 끝 (1, 1) 아래에 기둥 (1, 0)이 있으니 괜찮다.
2단계 · 가장 단순한 방법과 그 속도
명령마다 일단 수행하고, 모든 구조물이 규칙을 지키는지 확인한다. 어기는 것이 있으면 되돌린다. 구조물은 많아야 1,000개, 명령도 1,000개라 확인은 100만 번 정도다. 된다.
3단계 · 핵심 아이디어
- 설치: 새 구조물을 넣은 뒤 그것만 확인하면 된다. 무언가를 더해서 다른 구조물이 서 있을 근거가 사라지는 일은 없다.
- 삭제: 지운 뒤 남은 모든 구조물을 확인한다. 지운 것에 기대던 구조물이 있을 수 있다. 하나라도 어기면 다시 넣는다.
- 집합에 튜플로 담아 두면 “여기에 기둥이 있나”를
(x, y, 0) in S로 바로 본다. - 마지막에
sorted하면 (x, y, 종류) 순서로 정렬되어 “기둥 먼저”(0이 1보다 앞)가 저절로 된다.
4단계 · 코드 흐름
- 구조물 집합 S를 비운다.
- “(x, y, a)가 지금 서 있을 수 있나” 함수를 만든다(1단계의 규칙).
- 명령마다: 설치면 넣고 그것을 확인, 어기면 뺀다. 삭제면 빼고 전체를 확인, 어기는 것이 있으면 다시 넣는다.
- S를 정렬해 리스트로 돌려준다.
5단계 · 파이썬 코드
def solution(n, build_frame):
S = set()
def ok(x, y, a):
if a == 0: # 기둥
return y == 0 or (x, y - 1, 0) in S or (x - 1, y, 1) in S or (x, y, 1) in S
# 보
return (x, y - 1, 0) in S or (x + 1, y - 1, 0) in S or \
((x - 1, y, 1) in S and (x + 1, y, 1) in S)
for x, y, a, b in build_frame:
if b == 1: # 설치
S.add((x, y, a))
if not ok(x, y, a):
S.remove((x, y, a))
else: # 삭제
S.remove((x, y, a))
if not all(ok(*s) for s in S): # 남은 것이 모두 괜찮은가
S.add((x, y, a))
return [list(s) for s in sorted(S)]
ok(*s): 튜플 (x, y, a)를 풀어 세 인자로 넘긴다.\: 한 줄이 길어 다음 줄로 이어 쓴다는 표시다.- 벽면 밖이나 바닥에 보를 놓는 명령은 주어지지 않는다고 문제가 보장해서 따로 검사하지 않는다.
6단계 · 실행 추적
예시 1의 앞부분(n = 5)
| 명령 | 해 본 뒤 확인 | 결과 |
|---|---|---|
| 기둥 (1, 0) 설치 | 바닥이라 괜찮다 | 설치 |
| 보 (1, 1) 설치 | 왼쪽 끝 아래 기둥 (1, 0) | 설치 |
| 기둥 (2, 1) 설치 | 보 (1, 1)의 오른쪽 끝 위 | 설치 |
| 보 (2, 2) 설치 | 왼쪽 끝 아래 기둥 (2, 1) | 설치 |
| 기둥 (5, 0), (5, 1) 설치 | 바닥, 기둥 위 | 설치 |
| 보 (4, 2) 설치 | 오른쪽 끝 아래 기둥 (5, 1) | 설치 |
| 보 (3, 2) 설치 | 양옆에 보 (2, 2)와 (4, 2) | 설치 |
결과는 [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]이다.
7단계 · 복잡도와 흔한 실수
명령 C개마다 많아야 구조물 수(≤ C)만큼 확인하니 \(O(C^2)\), 약 100만 번이다.
- 삭제할 때 지운 것 주변만 확인하다 조건을 빠뜨린다. 전체를 확인하면 안전하다(이 크기에서는 충분히 빠르다).
- 보의 “양옆 보” 조건을 한쪽만 본다. 양쪽 모두 있어야 한다.
- 기둥이 보 위에 서는 두 경우((x − 1, y)의 보, (x, y)의 보) 중 하나를 빠뜨린다.
-
프로그래머스 스쿨, “기둥과 보 설치” (https://school.programmers.co.kr/learn/courses/30/lessons/60061), 2026-09-30 조회. ↩