[프로그래머스 Lv.4] 행렬과 연산(파이썬) (카카오 2022 인턴쉽 테그 기출)

https://school.programmers.co.kr/learn/courses/30/lessons/118670?language=python3 

프로그래머스

초기 문제접근

 

그냥 구현으로 풀면 되는 거 아닌가?

ShiftRow는 마지막 row를 빼고 앞으로 넣어주면되고

Rotate는 복잡하긴 하지만 구현그대로 해주면 될 거 같은데?

 

# from copy import deepcopy
# from collections import deque

# dx=[0,1,0,-1]
# dy=[1,0,-1,0]

# def shift(rc):
#     po=rc.pop()
#     rc.insert(0,po)
#     return rc
# 정확도는 통과했으나 시간효율성이 막힌 방법
# def ro(rc):

#     n=len(rc)
#     m=len(rc[0])
#     tmp=deepcopy(rc)

#     sx,sy=0,1
#     px,py=0,0
#     d=0
#     flag=False
#     while True:
#         if (sx,sy)==(0,1):
#             if not flag:
#                 flag=True
#             else:
#                 break

#         tmp[sx][sy]=rc[px][py]

#         px,py=sx,sy

#         if  not 0<=sx+dx[d]<n or not 0<=sy+dy[d]<m:
#             d=(d+1)%4

#         sx+=dx[d]
#         sy+=dy[d]

#     return tmp

# 이렇게 풀면 시간초과 이슈를 못빠져나옴
# def ro(rc):
#     n=len(rc)
#     m=len(rc[0])
#     q=deque()
#     flag=False
#     sx,sy=0,0
#     d=0
#     while True:
#         if (sx,sy)==(0,0):
#             if not flag:
#                 flag=True
#             else:
#                 break

#         q.append(rc[sx][sy])


#         if  not 0<=sx+dx[d]<n or not 0<=sy+dy[d]<m:
#             d=(d+1)%4

#         sx+=dx[d]
#         sy+=dy[d]

#     q.rotate()

#     sx,sy=0,0
#     d=0
#     flag=False
#     while True:
#         if (sx,sy)==(0,0):
#             if not flag:
#                 flag=True
#             else:
#                 break

#         rc[sx][sy]=q.popleft()


#         if  not 0<=sx+dx[d]<n or not 0<=sy+dy[d]<m:
#             d=(d+1)%4

#         sx+=dx[d]
#         sy+=dy[d]

#     return rc

# def solution(rc, operations):
#     answer = [[]]

#     for operation in operations:

#         if operation=="Rotate":

#             rc=ro(rc)


#         elif operation=="ShiftRow":

#             rc=shift(rc)

#     return rc

 

결과

 

정확성은 다 맞았으나

효용성에서 2개만 통과하고 나머지는 전부 시간초과.

deque로 쓰라는 힌트를 얻었으나

여전히 시간초과...

 

힌트

deque로 링크드리스트를 만들어라

 

카카오측에서 제시한 풀이방안.

저처럼 직접 쌩구현으로 rotate을 시켜준다면

operation이 길어지기나

행렬의 크기가 처음부터 최대로 주어진다면

시간초과가 뜰 수 밖에 없습니다.

하지만 저렇게 링크드리스트로 구현하면

각각의 꼬리,머리를 넣어주고 뺴주는 식으로 구할 수 있으니

시간을 훨씬 절약해줍니다.

 

개선된 코드

from collections import deque


def solution(rc, operations):
    # 행 수, 열 수
    r_len, c_len = len(rc), len(rc[0])

    # ShiftRow 연산을 위해 행별로 관리 [양쪽 원소를 제외한 행들, ...]
    rows = deque(deque(row[1:-1]) for row in rc)
    # Rotate 연산을 위해 바깥쪽 원소들(열별)을 관리 [첫열, 마지막열]
    out_cols = [deque(rc[r][0] for r in range(r_len)),
                deque(rc[r][c_len - 1] for r in range(r_len))]

    for operation in operations:
        if operation == "ShiftRow":
            rows.appendleft(rows.pop())

            out_cols[0].appendleft(out_cols[0].pop())
            out_cols[1].appendleft(out_cols[1].pop())

        else:
            rows[0].appendleft(out_cols[0].popleft())
            out_cols[1].appendleft(rows[0].pop())
            rows[-1].append(out_cols[1].pop())
            out_cols[0].append(rows[-1].popleft())

    answer = []
    for r in range(r_len):
        answer.append([])
        answer[r].append(out_cols[0][r])
        answer[r].extend(rows[r])
        answer[r].append(out_cols[1][r])
    return answer

 

후기

처음에 쌩구현이라 Lv.4가 이렇게 쉽나?생각했지만...

역시나...

이걸 시험장에서 어떻게 생각할까 싶긴 하지만...

공부하자...