[Codility] Recursion과 nonlocal을 활용한 magicSquare 풀이

Codility Almost Magic Square (coder of Rivia challenge)

변수의 범위(scope)

코딩테스트 문제를 많이 풀어보면서 global이 아닌 nonlocal 변수들을 자주 사용하게 됐다. 변수의 영향 범위(variable scope)에 대해서 익숙해졌다.

• global: 전역
• local: 함수 내부 (지역)
• nonlocal: 함수 외부의 값을 가져오면서 그 값이 글로벌은 아닐 경우 (= 바깥 함수 내에서 정의된 변수인 경우)

DFS 등을 recurse 방식으로 돌려줄 때 함수 안으로 가져와서 수정은 하지만 바깥 쪽에 계속 유지되어야 하는 경우(ex. visited map)나 바깥 함수에서 정의된 target 값들을 내부 함수에서도 사용해줘야 한다면 nonlocal을 사용하기 좋다.

이 문제는 코딜리티 콘테스트 문제라서 자세히 포스팅 하지는 않지만, (그만큼 좋은 풀이도 아닌 것 같긴 하다) 어디에 답이 포스팅되어 있지 않기 때문에 다른 사람들에게도 조금 도움이 되지 않을까 하여 짧게 남겨둔다.

Question

3*3 사각형과 그 안의 숫자들 [0,2,3,4,1,1,1,3,1]이 주어졌을 때 액션을 취해서 6개 라인(가로 세 줄, 세로 세 줄) 각각의 합을 같게 만들어주고, 그 결과를 출력. 주어진 숫자 list의 인덱스와 그림에서 각 칸 하단에 쓰인 숫자가 같다.
여기서의 액션은 한번에 한 칸의 숫자를 1씩 증가시킨다는 것

Solution

• 같아져야 할 라인의 index [0,1,2], [3,4,5], ..., [2,5,8] -> list1
• 각 라인들의 합 [5,6,5,...,5]
• Target: 각 라인들의 합이 target이 되어야 함. 빼줄 순 없으니 라인 합 중 가장 큰 값으로
• Target까지 부족한 값: [1,0,1,...,1] 각 라인을 얼마나 더 채워야 하는지? -> list2
• 1번 리스트의 인덱스와 2번 리스트의 인덱스가 같기 때문에 매칭이 가능해진다. 2번 리스트에서 루프를 돌면서 두 개를 선정하고 각각 채워야 할 값이 있으면서 동시에 갖고 있는 인덱스가 있다면 해당 공통 인덱스 값을 올려주면서 두 라인을 동시에 채워준다.
• 위 과정을 recursion으로 반복하다가 list2의 sum이 0가 된다면(더 채워야 할 라인이 없다면) 끝

1번 리스트와 2번 리스트를 만들어주고 채워야 할 라인들만 각 리스트에 남겨놓은 후에 아래 함수를 recursion 실행하면 된다.

    def helper():
        nonlocal list_idx, list_target # index들의 리스트와 채워야 할 값들의 리스트
        for i in range(len(list_idx)-1):
            for j in range(i+1, len(list_idx)):
                # i, j의 채워야할 값들이 남아있고, 둘의 공통 부분이 있다면
                if list_target[i] and list_target[j] and (set(list_idx[i]) & set(list_idx[j])):
                    add_idx = list(set(list_idx[i]) & set(list_idx[j]))[0] # 추가해야 할 index
                    val = min(list_target[i], list_target[j]) # 최대 몇 까지 추가할 수 있는지
                    A[add_idx] += val
                    list_target[i]-=val
                    list_target[j]-=val
                    if sum(list_target)==0: return # 한번 작업하고 다 됐는지 확인
        helper() # 함수가 위에서 return 되지 않는다면 모두 채워진 게 아니기 때문에 다시 실행