[kakao] 자물쇠와 열쇠 문제풀이

자물쇠와 열쇠 문제풀이 (2019 1차 코딩테스트 3번 문제)

[kakao] 자물쇠와 열쇠 문제

코딩테스트 연습 - 자물쇠와 열쇠

 

이번 문제의 해결방법은 완전 탐색 입니다.

lock 배열

 

위의 key를 90도 회전했을 때의 모양

배열을 90도 돌리는 함수 입니다.

def rotate_90(key):
	row_len = len(key)
    col_len = len(key[0])
    # 3*3의 행렬의 모든 값을 0으로
    result =  [ [0] * row_len for _ in range(col_len)]
    for i in range(row_len):
    	for j in range(col_len):
        	result[j][n-i-1] = key[i][j]
    return result

 

위의 표를 보시면  result[j][n-i-1] = key[i][j]  가 이해가 될 것입니다.

 

 

 

완전 탐색을 수월하게 하기위해서는 lock의 크기를 3배이상으로 변경하면 계산이 쉬워집니다.

 

이때 가운데에 lock배열을 위치하고 나머지는 0으로 둡니다. (빨간 네모 모양처럼)

파란네모 처럼 1 +1 이되서 2로 변하게 되면 안됩니다. 만약, lock 배열의 모든 값이 모두 1이라면 자물쇠의 홈부분을 정확히 채운 것이라고 볼 수 있습니다.

 

 

- 알고리즘 순서 생각하기

90도 회전 함수 

자물쇠의 배열이 모두 1인지 확인 함수 

 

자물쇠의 배열 3배로 증가

3배로 증가시킨 자물쇠 배열 중간에 자물쇠 배열 값 넣기

4번 90도 돌았을때

  자물쇠에 키 넣기

     맞는지 확인

  자물쇠에 키 빼기

 

# 90도 회전함수
def rotate_90(key):
    row_len = len(key)
    col_len = len(key[0])

    rotate_result = [[0]*row_len for _ in range(col_len)]
    for i in range(row_len):
        for j in range(col_len):
            rotate_result[j][row_len-i-1] = key[i][j]

    return rotate_result

# 자물쇠의 배열이 모두 1인지 체크
def check(result_check):
    check_length  = len(result_check) // 3
    for i in range(check_length, check_length +3):
        for j in range(check_length, check_length +3):
            if result_check[i][j] != 1:
                return False
    return True

def solution(key, lock):
    key_len = len(key)
    lock_len = len(lock)

    # 자물쇠의 배열 3배로 증가 시키기    
    check_result = [ [0] * (lock_len * 3) for _ in range(lock_len * 3 ) ]
    
    # 3배로 증가시킨 배열 중간에 기존 자물쇠 넣기
    for i in range(lock_len):
        for j in range(lock_len):
            check_result[i+lock_len][j+lock_len] = lock[i][j]

    # 4번 90도 돌았을때
    for _ in range(4):
        key = rotate_90(key)
        for i in range(lock_len * 2):
            for j in range(lock_len * 2):
                # 자물쇠에 키 넣기            
                for x in range(key_len):
                    for y in range(key_len):
                        check_result[i+x][j+y] += key[x][y]
                # 맞는지 확인
                if check(check_result) == True:
                    return True

                # 자물쇠에 키 빼기
                for x in range(key_len):
                    for y in range(key_len):
                        check_result[i+x][j+y] -= key[x][y]

    return False