(2020 KAKAO Blind Recruitment) 자물쇠와 열쇠

Problem

카카오 홈페이지 코멘트

  • 정답률: 7.4%
  • 출제 의도
    • 2차원 배열을 다룰 수 있는지 파악
  • 해설
    • 제한이 크지 않기 때문에 가능한 모든 경우를 탐색해 볼 수 있습니다. 2차원 배열을 회전하는 함수를 하나 만들어 둔다면 코드를 더욱 깔끔하게 작성할 수 있습니다.
    • 최대 4번까지 배열을 회전시키면서 가능한 경우를 모두 탐색한 다음, 자물쇠의 모든 홈을 채워 비어있는 곳이 없도록 할 수 있다면 true를, 그렇지 않다면 false를 return 하면 됩니다.
    • key와 lock을 순서대로 맞춰보는 방법 중 하나는 우선 lock 배열을 가로, 세로 길이가 3배인 새로운 배열의 중앙 부분으로 옮긴 후, key 배열을 새로운 배열의 좌측 상단부터 순서대로 이동시키면서 겹치는 부분만 확인해보면 됩니다. 이때, 겹치는 부분은 자물쇠의 모든 홈이 채워지더라도, 겹치지 않는 부분에 여전히 자물쇠의 홈 부분이 남아있을 수 있으므로 모든 홈이 채워졌는지를 정확히 확인해야 합니다

My solution

def solution(key, lock):
    M = len(key)
    N = len(lock)
    key = [key]

     def init(M): # 배열 0으로 초기화 생성
        res = []
        for m in range(M):
            temp = []
            for n in range(M):
                temp.append(0)
            res.append(temp)
        return res

     def padding(lock, N, M): # sliding을 위한 0으로 padding
        T = N + 2 * (M - 1)
        res = []
        for m in range(T):
            temp = []
            for n in range(T):
                temp.append(0)
            res.append(temp)

         for i in range(N):
            for j in range(N):
                res[i + M - 1][j + M - 1] = lock[i][j]

         return res

     def check(key, lock_padding): # key와 padding 결과를 비교하여 check
        import copy
        T = len(lock_padding)
        M = len(key)
        for gap1 in range(T - M + 1):
            for gap2 in range(T - M + 1):
                res = True
                cand_padding = copy.deepcopy(lock_padding)
                for p in range(M):
                    for q in range(M):
                        cand_padding[p + gap1][q + gap2] += key[p][q]
                check_area = []
                for p in range(M - 1, T - M + 1):
                    temp = []
                    for q in range(M - 1, T - M + 1):
                        temp.append(cand_padding [p][q])
                    check_area.append(temp)

                 for p in range(len(check_area)):
                    for q in range(len(check_area)):
                        if check_area[p][q] != 1:
                            res = False
                            break
                    if res == False:
                        break
                if res == True:
                    return res
        return False

     # key 후보 다 뽑기
    for i in range(3):
        new_key = init(M)
        for p in range(M):
            for q in range(M):
                new_key[q][M - 1 - p] = key[-1][p][q]
        key.append(new_key)

     # lock padding
    lock_padding = padding(lock, N, M)

     answer = False
    for i in range(4):
        cand_key = key[i]
        if check(cand_key, lock_padding) == True:
            return True

     return answer

댓글

댓글 쓰기