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 되지 않는다면 모두 채워진 게 아니기 때문에 다시 실행
Graduate School of DataScience, NLP researcher