[python/알고리즘] 프로그래머스 | 정수를 나선형으로 배치하기 | shallow copy | deep copy

프로그래머스 | 정수를 나선형으로 배치하기

문제

양의 정수 n이 매개변수로 주어집니다. n × n 배열에 1부터 n2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 return 하는 solution 함수를 작성해 주세요.

풀이

• 현재 위치 추적하기 row col
• 현재 위치에 따른 다음 행동 지정하기 ['R', 'D', 'L', 'U']
• 최대로 이동할 수 있는 인덱스 저장 max_col max_row

def solution(n):
    ans = [[0 for _ in range(n)] for j in range(n)]
    # 현재 위치
    row = 0
    col = 0
    # 테두리
    max_col = n - 1
    max_row = n - 1
    # 행동
    moves = ['R', 'D', 'L', 'U']
    move_index = 0
    
    ans[row][col] = 1
    for i in range(2, n**2 + 1):
        if moves[move_index % 4] == 'R':
            col += 1
            ans[row][col] = i
            if col == max_col:
                move_index += 1
        elif moves[move_index % 4] == 'D':
            row += 1
            ans[row][col] = i
            if row == max_row or ans[row+1][col] != 0:
                max_col -= 1
                move_index += 1
        elif moves[move_index % 4] == 'L':
            col -= 1
            ans[row][col] = i
            if col == 0 or ans[row][col-1] != 0:
                move_index += 1
                max_row -= 1
        else: # 'U'
            row -= 1
            ans[row][col] = i
            if ans[row-1][col] != 0:
                move_index += 1
    return ans

복사를 이용해 리스트를 만들 때 주의할 점

# 방법 1
a1 = [[0 for _ in range(4)] for j in range(4) ]
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

# 방법 2
a2 = [[0] * 4] * 4
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

두 방법 모두 결과는 같다. 문제는 값을 할당할 때 발생한다.

# 방법 1
a1[0][2] = 5
# [[0, 0, 5, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

# 방법 2
a2[0][2] = 5
# [[0, 0, 5, 0], [0, 0, 5, 0], [0, 0, 5, 0], [0, 0, 5, 0]]

방법 2는 shallow copy에 해당되어 4개의 리스트가 모두 같은 주소를 바라보고 있어서 하나의 리스트를 수정하면 다른 세 개의 리스트의 값도 바뀐다. 이를 방지하려면 방법 1과 같은 deep copy를 수행해야 한다. 깊은 복사는 내부에 객체들까지 모두 새롭게 copy하여 방법 2와 같은 문제를 방지해준다.

참고자료 - 위키독스 12. 얕은 복사(shallow copy)와 깊은 복사(deep copy)