행렬과 연산 (118670번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/118670

프로그래머스

 

 

프로그래머스 -  행렬과 연산 (118670번)

난이도 : Lv 4

Time Complexity : O( len(operations) )

알고리즘&자료구조 : Deque (덱, 데크)

 

---

2022 KAKAO TECH INTERNSHIP 기출문제이다.

 

 

★ 핵심 아이디어

행렬의 가장자리를 분리시키면, Deque를 활용해서 해결할 수 있다.

 

 

< 전체 코드 >

 

from collections import deque


def solution(rc, operations):
    R = len(rc)
    ul, ur, dl, dr = rc[0][0], rc[0][-1], rc[-1][0], rc[-1][-1]
    u, d = deque(rc[0][1:-1]), deque(rc[-1][1:-1])
    l, r = deque([rc[i][0] for i in range(1, R-1)]), deque([rc[i][-1] for i in range(1, R-1)])
    box = deque([deque(r[1:-1]) for r in rc[1:-1]])
    for oper in operations:
        if oper == 'Rotate':
            u.appendleft(ul)
            l.append(dl)
            d.append(dr)
            r.appendleft(ur)
            ul = l.popleft()
            dl = d.popleft()
            dr = r.pop()
            ur = u.pop()
        else:
            l.appendleft(ul)
            ul = dl
            dl = l.pop()

            box.appendleft(u)
            u = d
            d = box.pop()

            r.appendleft(ur)
            ur = dr
            dr = r.pop()
    
    rc = [[ul] + list(u) + [ur]]
    for _ in range(R-2):
        rc.append([l.popleft()] + list(box.popleft()) + [r.popleft()])
    rc.append([dl] + list(d) + [dr])
    return rc

---

 

① 행렬의 가장자리를 아래 그림처럼 분리시키고,

각 자료구조를 모두 deque로 만들어준다.

(배열의 맨 앞과 맨 뒤에서 삽입 및 제거가 모두 가능해야 한다.)

 

 

R = len(rc)
ul, ur, dl, dr = rc[0][0], rc[0][-1], rc[-1][0], rc[-1][-1]
u, d = deque(rc[0][1:-1]), deque(rc[-1][1:-1])
l, r = deque([rc[i][0] for i in range(1, R-1)]), deque([rc[i][-1] for i in range(1, R-1)])
box = deque([deque(r[1:-1]) for r in rc[1:-1]])

 

 

 

② "Rotate"

아래 그림과 같이, 테두리를 한 칸씩 회전시킨다.

 

 

u.appendleft(ul)
l.append(dl)
d.append(dr)
r.appendleft(ur)
ul = l.popleft()
dl = d.popleft()
dr = r.pop()
ur = u.pop()

 

 

 

③ "ShiftRow"

아래 그림과 같이 행을 한 칸씩 아래로 이동시키고,

가장 아래 행은 맨 위로 올려준다.

 

 

l.appendleft(ul)
ul = dl
dl = l.pop()

box.appendleft(u)
u = d
d = box.pop()

r.appendleft(ur)
ur = dr
dr = r.pop()

 

 

 

④ 주어진 operations를 모두 수행하면,

deque로 변환된 배열들을 모두 다시 list로 바꿔주고

원래 모양에 맞춰서 출력해준다.

 

rc = [[ul] + list(u) + [ur]]
for _ in range(R-2):
    rc.append([l.popleft()] + list(box.popleft()) + [r.popleft()])
rc.append([dl] + list(d) + [dr])
return rc