행렬과 연산

문제 보기 · Level 4 · 2022 KAKAO TECH INTERNSHIP · 정답률 14% · 푼 사람 1,351명 (2026-09-30 기준)¹

문제

행렬에 두 연산을 차례로 한다.

ShiftRow: 모든 행을 아래로 한 칸 민다. 마지막 행은 첫 행이 된다.
Rotate: 바깥 테두리(첫 행, 첫 열, 끝 행, 끝 열)의 원소를 시계 방향으로 한 칸 돌린다.

모든 연산을 마친 행렬을 돌려준다.

행 수, 열 수 각각 2 ~ 50,000, 원소 수(행 × 열) 4 ~ 100,000
연산 1 ~ 100,000개

풀이

막히면 한 단계씩 펼친다.

필요한 개념

큐와 덱: 행렬을 “첫 열”, “끝 열”, “행마다의 가운데 부분” 세 덩어리의 덱으로 나누면, 두 연산이 모두 양 끝에서 넣고 빼기 몇 번으로 끝난다.

1단계 · 작은 예로 손으로 풀기

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]에 Rotate를 하면 테두리 1, 2, 3, 6, 9, 8, 7, 4가 시계 방향으로 한 칸씩 옮겨 [[4, 1, 2], [7, 5, 3], [8, 9, 6]]이 된다. 가운데 5는 그대로다.

테두리에서 움직이는 것은 결국 네 모서리를 건너가는 원소 네 개뿐이다. 첫 행 안의 원소들은 한 칸씩 오른쪽으로 밀릴 뿐이다. 첫 행 가운데 부분을 덱으로 두면 “왼쪽 끝에 하나 넣고 오른쪽 끝에서 하나 빼기”가 곧 한 칸 밀기다.

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

연산마다 행렬을 그대로 바꾸면 ShiftRow는 행을 모두 옮기고, Rotate는 테두리를 모두 옮긴다. 테두리는 최대 약 10만 칸이라 연산 10만 번이면 100억 번에 가깝다. 정확성(원소 1만, 연산 100)은 통과해도 효율성은 못 넘는다.

3단계 · 핵심 아이디어

행렬을 세 덩어리로 나눈다.

left: 첫 열(위에서 아래로)을 담은 덱
right: 끝 열을 담은 덱
mid: 행마다 가운데 부분(첫·끝 열 제외)을 덱으로 두고, 그 덱들을 다시 덱에 담는다

그러면 두 연산이 모두 \(O(1)\)이다.

ShiftRow: 세 덩어리 모두 “맨 뒤를 빼서 맨 앞에 넣기” 한 번씩.
Rotate: 모서리를 건너는 네 원소만 옮긴다.
1. left의 맨 위 → mid[0]의 맨 앞(첫 행이 오른쪽으로 밀림)
2. mid[0]의 맨 뒤 → right의 맨 위(끝 열이 아래로 밀림)
3. right의 맨 아래 → mid[−1]의 맨 뒤(끝 행이 왼쪽으로 밀림)
4. mid[−1]의 맨 앞 → left의 맨 아래(첫 열이 위로 밀림)

열이 2개면 mid의 덱들이 비어 있어, 1에서 넣은 원소가 2에서 바로 빠져 right로 간다. 그래도 맞게 돈다.

4단계 · 코드 흐름

left, right, mid를 만든다.
연산마다 위의 방법대로 양 끝에서 넣고 뺀다.
행마다 [left[i]] + mid[i] + [right[i]]로 다시 이어 붙인다.

5단계 · 파이썬 코드

from collections import deque

def solution(rc, operations):
    left = deque(row[0] for row in rc)
    right = deque(row[-1] for row in rc)
    mid = deque(deque(row[1:-1]) for row in rc)
    for op in operations:
        if op == "ShiftRow":
            left.appendleft(left.pop())
            right.appendleft(right.pop())
            mid.appendleft(mid.pop())
        else:                                      # Rotate
            mid[0].appendleft(left.popleft())
            right.appendleft(mid[0].pop())
            mid[-1].append(right.pop())
            left.append(mid[-1].popleft())
    return [[left[i]] + list(mid[i]) + [right[i]] for i in range(len(rc))]

mid[0], mid[-1]: 덱의 양 끝 원소 보기는 \(O(1)\)이다. 가운데(mid[i])는 마지막에 한 번씩만 본다.
deque(row[1:-1]): 행의 둘째부터 끝에서 둘째까지를 덱으로 만든다.

6단계 · 실행 추적

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]에 Rotate 한 번. 처음에는 left = [1, 4, 7], right = [3, 6, 9], mid = [[2], [5], [8]]이다.

단계	옮긴 원소	left	right	mid[0]	mid[−1]
1	1: left 위 → mid[0] 앞	[4, 7]	[3, 6, 9]	[1, 2]	[8]
2	2: mid[0] 뒤 → right 위	[4, 7]	[2, 3, 6, 9]	[1]	[8]
3	9: right 아래 → mid[−1] 뒤	[4, 7]	[2, 3, 6]	[1]	[8, 9]
4	8: mid[−1] 앞 → left 아래	[4, 7, 8]	[2, 3, 6]	[1]	[9]

이어 붙이면 [[4, 1, 2], [7, 5, 3], [8, 9, 6]]이다.

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

만들고 되돌리는 데 \(O(RC)\), 연산마다 \(O(1)\)이다. 원소 10만 개, 연산 10만 개로 재 보니 0.2초가 안 걸렸다.

연산마다 행렬 전체를 바꿔 효율성에서 시간 초과가 난다.
가운데 부분을 행마다가 아니라 한 덩어리 리스트로 두어 ShiftRow가 느려진다.
Rotate의 네 이동 순서를 섞어, 방금 옮긴 원소를 다시 옮긴다.
열이 2개인 경우를 따로 처리하다 틀린다. 위 방식은 따로 처리할 필요가 없다.

검증: 문제의 예시 3개를 통과했고, 6단계의 Rotate 결과와 열이 2개인 경우를 확인했다. 무작위 입력 2,000개(행·열 2 ~ 5)에서 “테두리 좌표를 모아 직접 돌리는” 풀이와 결과가 같았다. 2 × 50,000, 50,000 × 2, 316 × 316 행렬에 연산 10만 번의 시간도 쟀다 — 11_pg118670_p1.py

프로그래머스 스쿨, “행렬과 연산” (https://school.programmers.co.kr/learn/courses/30/lessons/118670), 2026-09-30 조회. ↩