2022 KAKAO TECH INTERNSHIP 풀이

Level 1 - 성격 유형 검사하기 풀이
Level 2 - 두 큐 합 같게 만들기 풀이
Level 3 - 코딩 테스트 공부 풀이
Level 3 - 등산코스 정하기 풀이
Level 4 - 행렬과 연산 풀이

프로그래머스 - 행렬과 연산 링크
(2022.10.27 기준 Level 4)

문제

모든 행을 아래쪽으로, 마지막 행은 1번째 행으로 옮기는 ShiftRow 연산과 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸씩 옮기는 Rotate 연산이 있다.
행렬 rc를 여러 연산이 담겨져 있는 operations 순서대로 연산을 하고난 후의 행렬 상태 반환

알고리즘

문제 자체는 심플하다. 연산 구현
다만, 구현 자체가 생각이 많이 필요하다.

풀이

rc의 행과 열 길이의 곱은 최대 100,000. operations의 최대는 100,000. 그대로 구현하면 터진다.

이 문제 정말 어렵다.
그래서 난 공식 해설을 참고하면서 풀었다.
해설 중 제일 키포인트가 되는 그림은 바로이 그림이다.

바로 이해가 가는 사람도 있을 것이지만 일단 부연 설명을 해보겠다.

이렇게 left, mid, right를 구분해보자. 그리고 각 구분한 구역은 전부 deque로 저장하자.
(mid 안에 행들도 전부 deque로)
그러면 ShiftRow 연산은 간단하다. pop 하여 appendleft 하면 된다.

if operation == 'ShiftRow':
    left.appendleft(left.pop())
    mid.appendleft(mid.pop())
    right.appendleft(right.pop())

그러면 Rotate는?

위 그림의 각 꼭짓점이 Rotate 연산인데 각 화살표를 코드로 나타내면 저렇게 된다.
바로 이해가 갈 것이다.

그리고 열의 개수가 2이면 중앙이 비니깐 오류나지 않을까 걱정할 수도 있지만 붙들어매도 된다.
빈 deque가 행의 개수만큼 넣어지기 때문에 연산엔 아무 문제가 없다.

코드

from collections import deque

def solution(rc, operations):
    row = len(rc) # 행의 개수
    col = len(rc[0]) # 열의 개수

    # 왼쪽, 중앙, 오른쪽 구역을 나눠야 한다.
    left = deque() # 왼쪽
    mid = deque() # 중앙
    right = deque() # 오른쪽
    for r in range(row):
        left.append(rc[r][0])
        mid.append(deque(rc[r][1:-1]))
        right.append(rc[r][-1])

    # 순서대로 연산 시행
    for operation in operations:
        if operation == 'ShiftRow':
            left.appendleft(left.pop())
            mid.appendleft(mid.pop())
            right.appendleft(right.pop())
        else:
            mid[0].appendleft(left.popleft())
            right.appendleft(mid[0].pop())
            mid[-1].append(right.pop())
            left.append(mid[-1].popleft())

    # 결과 반환을 위해 다시 행렬 형태로 되돌린다.
    result = []
    for r in range(row):
        result.append([left[r]] + list(mid[r]) + [right[r]])
    return result

여담

개인적으로 정말 어렵던 문제.
시행될 연산을 보고 어떻게 자료구조를 만들어낼 것인지 생각해내는게 익숙치가 않았다.
별 어려운 알고리즘도 아니면서 이렇게 어려운 문제를 만들어내다니.. 대단해 카카오