[알고리즘] 행렬 테두리 회전하기

"""
    1. 쿼리가 주어진다.
    2. 회전할 영역 확인 
    2-1. 가장 작은 수 확인
    3. 회전
    
    디버깅 하는 법
    1. 내가 짠 코드의 동작 방식을 예측한다.
    2. 실행해본다.
    3. 결과와 내 코드 사이의 차이를 찾는다.
    4. 보강한다.
"""


def solution(rows, columns, queries):
    answer = []
    matrix = [[y+(columns*x) for y in range(1, columns+1)] for x in range(rows)]
    
    if len(queries) == 1:
        return [min(queries[0])]
    
    for query in queries:
        # 회전할 영역 확인
        min_x = min(query[0], query[2]) - 1
        max_x = max(query[0], query[2]) - 1
        min_y = min(query[1], query[3]) - 1
        max_y = max(query[1], query[3]) - 1
        
        # 가장 작은 수 확인
        val_lst = []
                
        for y in range(min_y, max_y + 1):
            val_lst.append(matrix[min_x][y])
        for x in range(min_x + 1, max_x + 1):
            val_lst.append(matrix[x][max_y])
        for y in range(max_y - 1, min_y - 1, -1):
            val_lst.append(matrix[max_x][y])
        for x in range(max_x - 1, min_x, -1):
            val_lst.append(matrix[x][min_y])
        answer.append(min(val_lst))
        
        # 회전
        idx = len(val_lst) - 1
        for y in range(min_y, max_y + 1):
            if idx == len(val_lst):
                idx = 0
            matrix[min_x][y] = val_lst[idx]
            idx += 1
            if idx == len(val_lst) - 1:
                break
        for x in range(min_x + 1, max_x + 1):
            if idx == len(val_lst):
                idx = 0
            matrix[x][max_y] = val_lst[idx]
            idx += 1
            if idx == len(val_lst) - 1:
                break
        for y in range(max_y - 1, min_y - 1, -1):
            if idx == len(val_lst):
                idx = 0
            matrix[max_x][y] = val_lst[idx]
            idx += 1
            if idx == len(val_lst) - 1:
                break
        for x in range(max_x - 1, min_x, -1):
            if idx == len(val_lst):
                idx = 0
            matrix[x][min_y] = val_lst[idx]
            idx += 1
            if idx == len(val_lst) - 1:
                break
        
    return answer

알고리즘이 있다기 보단 구현에 가깝다.

동작 방식은 주석에 넣었다

회전하는 알고리즘

1. val_lst에 시계방향대로 원소를 집어넣는다.
2. matrix와 val_lst 원소들의 인덱스를 +1 시켜서 맵핑 시킨다.
3. 이때 특이 케이스는 시작 인덱스와 종료 인덱스이다.
4. 시작 인덱스의 경우 val_lst의 끝 원소여야 한다.
5. 두 번째 원소부터는 val_lst의 0번째 원소여야 한다.
6. 종료 인덱스의 경우에는 idx 가 val_lst의 끝에 온 경우에 종료 시킨다.

여기서 특이 케이스를 if문으로 처리하였고 일반적인 케이스들은 for문으로 처리하였다.

고찰

얼핏 보면 문제가 어렵고 복잡해 보인다.
그러나 분할 정복의 관점에서 다시 살펴보면 아래의 과정이 반복될 뿐이다.
1. 회전할 영역 지정
2. 최솟값 저장
3. 회전 반영
그렇기에 항상 문제에서 어떤 과정이 반복되는지 알 필요가 있다.
대표적으로 별 찍기 문제가 그렇다. 그런데 별 찍기 문제는 분할 정복으로 풀리지 않을 수도 있다. 그러나 분할 정복으로 가는 쪽으로 사고방식을 조정해야 한다. 그래야만 깔끔한 코드에 도달하지 않을까 생각한다.