[programmers] Lv3 고고학 최고의 발견 - Python

코딩테스트 연습 - 고고학 최고의 발견 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

<문제 풀이>

 질문하기의 힌트를 참고했다. 4번이상 회전은 하지않는다는 점과 첫째 줄에 대한 경우의 수만 체크하면 된다는 점이다. 이를 이용하여 코드를 작성했다.

 첫번째 줄에 대한 경우의 수를 만들기 위해 중복순열을 이용하여 case를 만들며 체크를 했다. 그리고 시간을 줄이기 위해 깊은 복사는 slicing으로 진행을 했다. 이전 까지는 deepcopy를 사용하여 깊은 복사를 진행했지만 slicing이 더 빠르다는 것을 스터디원을 통해 알게 되었다. 입력되는 2차원 배열을 그냥 slicing 했다가 맞왜틀을 시전하며 시간낭비를 했다;; 아래 코드로 변경 후 통과할 수 있었다. 1차원처럼 slicing을 한다면 내부는 깊은 복사가 이루어지지 않는 다는 점!!! 이런 실수를 줄일 수 있는 좋은 계기가 된 것 같다. 

 첫번째 줄에 대해 조작이 이루어졌다면 나머지는 해당 라인을 회전하여  12시로 가게끔 만든 후 마지막 라인을 체크하여 모두 12시에 갔는지 확인하고, 확인이 되었다면 answer에 최솟값을 갱신하면 된다. 

 

 

 

<Code>

from itertools import product


def solution(clockHands):
    answer = 9876543210
    n = len(clockHands)

    dy = [-1, 1, 0, 0, 0]
    dx = [0, 0, -1, 1, 0]

    def rotate(a, b, t, arr):
        for k in range(5):
            y, x = a + dy[k], b + dx[k]
            if 0 <= y < n and 0 <= x < n:
                arr[y][x] = (arr[y][x] + t) % 4

    for case in product(range(4), repeat=n):    # 첫째줄 최대4번까지 회전 한다는 가정 하에 모든 경우의 수를 만든다.
        arr = [i[:] for i in clockHands]    # 깊은 복사는 deepcopy 보다 slicing 이 빠름

        for j in range(n):    # case 를 가지고 첫번째 줄만 회전 시킨다
            rotate(0, j, case[j], arr)

        result = sum(case)    # 첫번째 줄 조작 횟수의 합

        for i in range(1, n):    # 두번째 줄부터 체크
            for j in range(n):
                if arr[i-1][j]:    # 12시 가있지 않은 시계만 조작
                    temp = 4 - arr[i-1][j]    # 12시에 가도록 하기 위한 조작 횟수
                    rotate(i, j, temp, arr)    # 회전
                    result += temp    # 조작 횟수 누적

        if sum(arr[n-1]):    # 마지막 라인에 12시를 향하지 않는 시계가 존재
            continue    # pass

        answer = min(answer, result)    # 시계가 모두 12시를 가리킨다면 answer을 최솟값으로 갱신

    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.