[프로그래머스] 카카오 2020 blind recruitment - 자물쇠와 열쇠

문제

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

 

풀이

브루트포스는 늘 정말 이 방법 뿐일까..? 싶어서 주저하게 된다.

M과 N이 모두 20 이하의 수라서 브루트포스로 다 돌려줬다.

 

lock에 key를 끼워봐야하는데, 키가 락 위에 일부분만 걸쳐있어도 되는거라 락의 주위로 빈 공간을 만들어주는게 포인트인 문제.

사실 그렇게 풀지 않아도 되는 방법이 있겠지만 빈 공간을 만들어주면 포문만 돌리면 돼서 편리하다. 

 

포문이 많으면 범위를 자꾸 실수해서 그러지 않으려고 옆에 그림을 그려두고 했는데도 실수했다.

시험 당일엔 사소한 실수에 말린다 ㅜㅜ 만약 답이 안나온다면 차분하게 다시 되짚어볼것! 

 

# 돌리는 함수
def rotate(key):

    N = len(key)
    new = [[0 for _ in range(N)] for _ in range(N)]

    for r in range(N):
        for c in range(N):
            new[c][N-1-r] = key[r][c]

    return new



def solution(key, lock):

    M = len(key)
    N = len(lock)

    new = key

    # key를 돌리기 위한 포문
    for _ in range(4):
        new = rotate(new)

        # lock을 위한 포문 (key의 (0.0)이 올 위치 정하기)
        for i in range(M+N-1):
            for j in range(M+N-1):

                # key를 넣어보기 편하게 위-아래-양옆으로 확장
                newlock = [[0 for _ in range(N - 2 + (2 * M))] for _ in range(N - 2 + (2 * M))]
                for a in range(N):
                    for b in range(N):
                        newlock[M-1+a][M-1+b] = lock[a][b]

                # key를 위한 포문
                for r in range(M):
                    for c in range(M):
                        newlock[i+r][j+c] += new[r][c]



                # 확인
                flag = True
                for nr in range(M-1, M+N-1):
                    for nc in range(M-1, M+N-1):
                        if newlock[nr][nc] != 1:
                            flag = False
                            break

                    if not flag:
                        break

                if flag:
                    return flag

    return flag

 

 

 

로테이트 함수는 많이 나오니 아예 통째로 외워주는게 편하다.

for r in range(N):
	for c in range(N):
		new[c][N-1-r] = key[r][c]