행렬 테두리 회전하기(프로그래머스)

문제 

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

프로그래머스

 

 

 

 

문제 접근 방식

회전에 필요한 알고리즘이 따로 있지는 않고 주어진 조건에 맞춰 푸는 구현 문제이다. 주어진 구간을 시계방향으로 회전시키고 해당 회전 구간에서 가장 작은 수를 계속해서 구해야한다. 

 

시계 방향으로 회전시킬 때 다양한 구현 방법이 있겠지만, 행렬의 테두리를 원형으로 생각했기 때문에 원형 큐와 연관지으려 했고 그 부분에서 아이디어를 얻었다. 테두리의 좌측 상단을 가장 첫번째라고 가정하고 시계방향으로 순서를 고정하면 각 (행,열) 쌍에 대한 값들이 존재한다.  여기서 회전을 하게 된다면 기존 값들을 한칸씩 밀리게 되고 기존 마지막 값이 맨 앞으로 오게 된다(아래 그림 참조)

 

따라서, 위치와 값에 대해 각각 리스트, 원형 큐를 두고 회전시 원형 큐의 마지막 값을 첫번째 값으로 이동시키고, 갱신된 [  (행,열) : 값 ] 을 배열에 반영해주면 회전이 완료된다.

 

 

시간 복잡도

쿼리의 개수만큼 for문을 돌며, 테두리를 회전할 때 [좌>우, 상>하, 우>좌, 하>상] 을 순회해야한다. 쿼리의 개수를 q, 가로 세로의 개수를 r,c 라고 하면 전체 시간복잡도는 O(q(r+c)) 이다. q의 최댓값은 1e4, r과 c의 최댓값은 100이므로 시간내에 동작한다.

 

 

코드

def rotate(arr, query):
    t, l, b, r = query
    locs = []
    values = []

    ## 테두리를 돌면서 [위치],[값]을 각각 locs,values에 차례대로 저장한다
    # 좌>우
    for j in range(l, r):
        locs.append((t, j))
        values.append(arr[t][j])
    # 상>하
    for i in range(t, b):
        locs.append((i, r))
        values.append(arr[i][r])
    # 우>좌
    for j in range(r, l, -1):
        locs.append((b, j))
        values.append(arr[b][j])
    # 하>상
    for i in range(b, t, -1):
        locs.append((i, l))
        values.append(arr[i][l])

    # values의 마지막 값을 앞으로 보내서 나머지 값들이 밀리도록 한다
    # 밀린 값들을 기존 locs와 맵핑시키면 회전이 완료된다
    values.insert(0, values.pop(-1))
    for i in range(len(locs)):
        y, x = locs[i]
        arr[y][x] = values[i]

    # values 중 최솟값을 반환한다
    # 위에서 values를 초기화할 때 최솟값을 구할 수 있지만 코드의 간결함을 위해 아래와 같이 최솟값을 구했다
    return min(values)


def solution(rows, columns, queries):
    arr = [[(i - 1) * columns + j for j in range(columns + 1)] for i in range(rows + 1)]
    answer = []
    
    # 쿼리를 통해 행렬을 변경하고, 그중 최솟값을 answer에 넣어준다.
    for query in queries: 
        answer.append(rotate(arr, query))

    return answer