[プログラマー60059]2020公開求人3番ロックと鍵


質問する


[プログラマ60059]ロックとキー

方法


M,Nは20未満なので、完全にブラウズして書き込みます!

プロセス全体

for 90도씩 회전:
	# key 반시계방향으로 돌리기
    for key 한칸씩 이동하며 자물쇠 홈 채우기:
    	# 딱 맞으면 True 리턴

# 딱 맞는 경우가 없으면 False 리턴

コード#コード#

def solution(key, lock):
    M,N = len(key),len(lock) # 3<=M<=N<=20
    
    # lock길이의 3배인 board를 만들어 가운데를 lock값으로 초기화
    board = [ [0]*3*N for _ in range(3*N) ]
    for i in range(N):
        for j in range(N):
            board[N+i][N+j]=lock[i][j]
           
     
    newkey = [ [0]*M for _ in range(M)] 
    
    # key 90도씩 회전시키고 모든 경우에 대하여 홈 채우기
    for dir in range(4):
        
        # key 반시계방향으로 돌리기
        for i in range(M):
            for j in range(M):
                newkey[i][j] = key[j][M-1-i]
      
        ### 한칸씩 이동하며 홈 채우기
        for X in range(N-M+1,2*N): #N-M+1부터 2*N-1까지
            for Y in range(N-M+1,2*N):
                
                newboard = [ board[i][:] for i in range(3*N) ]  # 처음 board 값 복사
                
                # 자물쇠에 열쇠 끼워넣기
                for i in range(M):
                    for j in range(M):
                        newboard[X+i][Y+j] += newkey[i][j]
                
                # 딱 맞는지 체크
                check = 0
                for i in range(N,2*N):
                    for j in range(N,2*N):
                        if newboard[i][j]==1: 
                            check += 1
                if check==N**2:
                    return True
                
        key = [ newkey[i][:] for i in range(M) ]  # key에 현재 newkey값 복사해야 이따 재활용할 수 있음
 
    return False

ちょっとしたミス


「チェックが適切かどうか」の部分が間違っています.
# 딱 맞는지 체크
if sum(map(sum,newlock))==(N**2):
    return True
このコードは、ロックもキーも回転する場合を考慮していません(newboard[i][j]==2)
そのため、以下のように変更されました.
# 딱 맞는지 체크
check = 0
for i in range(N,2*N):
    for j in range(N,2*N):
    # 정확히 1일 때만
    if newboard[i][j]==1: 
        check += 1
if check==N**2:
    return True

結果