[Programmers] level4 - 행렬과 연산 (Python) : 2022 카카오 테크 인턴십 (75점 / 100점)

▶행렬과 연산 - 2022 카카오 테크 인턴십 (level 4)

▶문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.

• ShiftRow
  • 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.)
  • ShiftRow의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다.
    • 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다.

• Rotate
  • 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다.
  • 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다.
  • 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀려난다는 것을 의미합니다. 즉, 다음 4개의 연산이 동시에 시행됩니다.
    • 첫 행에서 끝 열에 있는 원소를 제외한 첫 행의 모든 원소는 오른쪽으로 한 칸 이동합니다.
    • 끝 열에서 끝 행에 있는 원소를 제외한 끝 열의 모든 원소는 아래쪽으로 한 칸 이동합니다.
    • 끝 행에서 첫 열에 있는 원소를 제외한 끝 행의 모든 원소는 왼쪽으로 한 칸 이동합니다.
    • 첫 열에서 첫 행에 있는 원소를 제외한 첫 열의 모든 원소는 위쪽으로 한 칸 이동합니다.
  • Rotate의 예 

    

    • 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 Rotate를 한 번 시행한 뒤의 행렬입니다.
    • 바깥쪽에 있는 값들이 시계 방향으로 한 칸씩 이동한 것을 확인할 수 있습니다.

당신은 행렬에 연산을 여러 번 시행하려고 합니다.
행렬의 초기 상태를 담고 있는 2차원 정수 배열 rc, 시행할 연산을 순서대로 담고 있는 문자열 배열 operations가 매개변수로 주어졌을 때, 연산을 차례대로 시행한 후의 행렬 상태를 return 하도록 solution 함수를 완성해주세요.

 

▶입출력 예

입출력 예#1

위 그림은 ”Rotate”와 ”ShiftRow”를 차례대로 실행한 결과입니다.

따라서 [[8, 9, 6], [4, 1, 2], [7, 5, 3]]을 return 해야 합니다.

 

입출력 예#2

위 그림은 ”Rotate”, ”ShiftRow”, "ShiftRow"를 차례대로 실행한 결과입니다.

따라서 [[8, 3, 3], [4, 9, 7], [3, 8, 6]]을 return 해야 합니다.

 

입출력 예#3

위 그림은 ”ShiftRow”, ”Rotate”, ”ShiftRow”, ”Rotate”를 차례대로 실행한 결과입니다.

따라서 [[1, 6, 7 ,8], [5, 9, 10, 4], [2, 3, 12, 11]]을 return 해야 합니다.

▶풀이

일단 이 문제를 맞히지 못했다.

하지만 100점 만점에 75점을 받았기에, 내 풀이도 공유하려고 한다.

 

일단 Rotate와 ShiftRow함수 두 개를 만들었다.

ShiftRow는 마지막을 pop 한 후에 appendleft 해주었다.

간단하게 끝났다.

 

Rotate는 앞서 문제를 하나 풀어서 기록했다.

2022.08.27 - [Programmers Code/coding test - level 2] - [Programmers] level2 - 행렬 테두리 회전하기 (Python) : 2021 Dev-Matching(상반기)

[Programmers] level2 - 행렬 테두리 회전하기 (Python) : 2021 Dev-Matching(상반기)

이 문제와 동일한 방식으로 풀었다.

 

일정한 횟수가 연속으로 ShiftRow 또는 Rotate 하게 된다면 똑같은 answer가 나온다.

그렇기에 그 부분의 반복을 없애준다면 시간적으로 효율적이라 생각했다.

 

그래서 solution함수 안에서 연속으로 나오는지 아닌지 판단하는 코드도 작성했다.

import copy
from collections import deque


def solution(rc, operations):
    def Rotate(rc):
        ans = [item[:] for item in rc]
        row = len(rc)
        col = len(rc[0])
        
        #윗줄 아랫줄
        for i in range(1, col):
            ans[0][i] = rc[0][i - 1]
            ans[row - 1][i - 1] = rc[row - 1][i]
        #오른쪽 왼쪽
        for i in range(1, row):
            ans[i][col - 1] = rc[i - 1][col - 1]
            ans[i - 1][0] = rc[i][0]
        
        return ans
        
        
    def ShiftRow(rc):
        ans = deque([item[:] for item in rc])
        n = len(rc)
        tmp = ans.pop()
        ans.appendleft(tmp)
        
        return list(ans)
    
    
    answer = rc
    rt, shift = 0, 0
    number = len(operations)
    
    for i in range(number):
        if operations[i] == 'Rotate':
            rt += 1
            if i + 1 != number:
                if operations[i + 1] == 'Rotate':
                    continue
                else:
                    rt %= (len(rc) * 2 + len(rc[0]) * 2 - 4)
                    for i in range(rt):
                        answer = Rotate(answer)
                    rt = 0
            else: #마지막 요청
                rt %= (len(rc) * 2 + len(rc[0]) * 2 - 4)
                for i in range(rt):
                    answer = Rotate(answer)
                    
        elif operations[i] == 'ShiftRow':
            shift += 1
            if i + 1 != number:
                if operations[i + 1] == 'ShiftRow':
                    continue
                else:
                    shift %= len(rc)
                    for i in range(shift):
                        answer = ShiftRow(answer)
                    shift = 0
            else:
                shift %= len(rc)
                for i in range(shift):
                    answer = ShiftRow(answer)
        
    return answer

이렇게 제출하니까 틀렸다고 나왔다.

정확성에서는 25/25으로 만점을 받았지만, 효율성에서 50/75로 만점을 받지 못해서 틀렸다.

하지만 다 틀리지는 않았기에, 어느 정도 점수를 받을 수 있지 않을까 생각한다.

어떻게 고쳐보아도 효율성 테스트 2, 4, 7이 시간 초과가 나온다.

제발 이 문제를 보는 누군가가 있다면, 나에게 팁을 주면 좋겠다.

Help me!