2023-04-01 알고리즘 복기록

프로그래머스

2021 Dev-Matching 백엔드 개발자: 행렬 테두리 회전하기

문제 정의

  • 행렬의 테두리 회전을 구현하는 문제이다.
  • queries 는 회전시킬 범위 (x1, y1, x2, y2) 에 해당하는 query 들을 리스트에 담고 있다.
    • [[2,2,5,4],[3,3,6,6],[5,1,6,3]]
  • 각 모서리에 해당하는 부분을 회전시킬 때, 이전에 회전시킨 상태가 다음 상태에 영향을 미치지 않는지 잘 고려해야 한다.

solution code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def solution(rows, columns, queries):
    a = [[columns * i + j for j in range(1, columns + 1)] for i in range(rows)]
    def rotate_matrix(a, query):
        x1, y1, x2, y2 = [elem - 1 for elem in query]
        save = a[x1][y1]
        mn = 10 ** 9
        # 왼쪽 세로줄 roate
        for i in range(x1, x2):
            a[i][y1] = a[i+1][y1]
            mn = min(mn, a[i+1][y1])
            
        # 하단 가로줄 rotate
        for j in range(y1, y2):
            a[x2][j] = a[x2][j+1]
            mn = min(mn, a[x2][j+1])
            
        # 오른쪽 세로줄 roate (역순으로)
        for i in range(x2, x1, -1):
            a[i][y2] = a[i-1][y2]
            mn = min(mn, a[i-1][y2])
            
        # 상단 가로줄 rotate
        for j in range(y2, y1, -1):
            a[x1][j] = a[x1][j-1]
            mn = min(mn, a[x1][j-1])
            
        a[x1][y1 + 1] = save
        mn = min(mn, save)
        
        return mn

    print("원본 행렬: ")
    print(*a, sep='\n')
    
    ans = []
    for query in queries:
        mn = rotate_matrix(a, query)
        ans.append(mn)
        
    print("회전된 행렬: ")
    print(*a, sep='\n')
    
    return ans

유의 사항

  • 앞서 언급한 상태 변화에 따라 연속적인 작업에 영향을 미치지 않도록 고려해야 한다. 원본 배열의 모든 값을 저장하는 별도의 tmp 배열을 선언한 후, 여기에서 값을 읽어오는 방법도 가능은 하고 문제 조건에 따르면 시간 초과가 나지는 않을 것이다.
  • 하지만, 이는 너무 비효율적이다. 따라서, 시계 방향으로 테두리를 회전시킬 때 영향을 받는 단 하나의 값 (위 코드의 경우 시작부분인 a[x1][y1] 에 해당) 을 save 변수에 임시로 저장한 뒤, 마지막에 이 저장된 값을 별도로 이용하는 로직을 사용하였다.

comments powered by Disqus