[프로그래머스] LEVEL3 자물쇠와 열쇠, python3, 2020 KAKAO BLIND RECRUITMENT

처음에 생각했던 알고리즘은 lock의 홈부분이 key의 부분집합인지 확인하는 것이었다.
하지만 부분집합이어도 성립하지 않는것들을 찾았기 때문에 더이상 진전이 없었다.

물론 처음부터 끝까지 key을 돌려가며 모든 경우를 확인하는 완전탐색의 방법도 생각했으나 그것보다 더 좋은 생각이 없을까 하는 생각에 구현하지는 않았다.

하지만 다른사람의 알고리즘을 보니 대부분 모든 배열을 확인하는 방식으로 하였다. 뛰어난 알고리즘도 좋지만 코딩테스트에는 답을 구현하는게 더 중요한듯하다.

첫번째로 수행한것은 key를 회전시키는 함수의 구현이었다.

def rot(key,M):
    #1 key[i][j]=key[j][i]
    tmp=[]
    for i in range(M):
        tmp_row=[]
        for j in range(M):
            tmp_row.append(key[j][i])
        tmp.append(tmp_row)
    #2 key[j][i] to inverse of left and right
    for i in range(M):
        tmp[i].reverse()
    return tmp

두번째로 수행한것은 lock을 가로세로 M-2만큼 확장시킨 배열을 저장하고 key를 한칸씩 옮겨가며 lock이 풀리는지 확인하는 함수를 구현하였다.

def check_elements(key,lock_exp,N,M,size_exp):
    r_w,c_w=0,0 # weight of row,col
    while True:
        # 0. copy lock_exp to tmp
        tmp=[[0]*size_exp for i in range(size_exp)]
        for i in range(size_exp):
            for j in range(size_exp):
                tmp[i][j]+=lock_exp[i][j]
        # 1. Add key to lock_exp
        for r in range(N):
            for c in range(N):
                tmp[r+r_w][c+c_w]+=key[r][c]
        
        # 2. Check lock
        br=0
        for i in range(M-1,N+M-1): # 2,3,4
            for j in range(M-1,N+M-1):
                if tmp[i][j] != 1:
                    br=1
                    break
            if br==1:
                chk=False
                break
            chk=True
        
        if (chk==True): 
            break       # while break
        elif (r_w==N+M-2) and (c_w==N+M-2):
            break       #while break
        elif (c_w==N+M-2):
            c_w=0       # while loop, initialize weight of col to 0
            r_w+=1      # plus 1 to weight of row
        else:   
            c_w+=1      # while loop, plus 1 to weight of col
    return chk

---

전체 코드는 다음과 같다

def solution(key, lock):
    answer = False
    M,N=len(key),len(lock)
    lock_exp=[]
    size_exp=N+2*M-2
    # lock을 크기가 (N+2*M-2)^2 인 배열로 확장
    for i in range(size_exp):
        tmp=[]
        for j in range(size_exp):
            if (i < M-1) or (i>N+M-2) or (j < M-1) or (j>N+M-2):
                tmp.append(0)
            else:
                tmp.append(lock[i-M+1][j-M+1])
        lock_exp.append(tmp)
    
    # 자물쇠가 맞는지 확인하고 안맞으면 회전
    for i in range(0,4): 
        chk=check_elements(key,lock_exp,N,M,size_exp)
        if chk==True:
            answer=chk
            break
        key=rot(key,M)
    return answer

def rot(key,M):
    #1 key[i][j]=key[j][i]
    tmp=[]
    for i in range(M):
        tmp_row=[]
        for j in range(M):
            tmp_row.append(key[j][i])
        tmp.append(tmp_row)
    #2 key[j][i] to inverse of left and right
    for i in range(M):
        tmp[i].reverse()
    return tmp

def check_elements(key,lock_exp,N,M,size_exp):
    r_w,c_w=0,0 # weight of row,col
    while True:
        # 0. copy lock_exp to tmp
        tmp=[[0]*size_exp for i in range(size_exp)]
        for i in range(size_exp):
            for j in range(size_exp):
                tmp[i][j]+=lock_exp[i][j]
        # 1. Add key to lock_exp
        for r in range(N):
            for c in range(N):
                tmp[r+r_w][c+c_w]+=key[r][c]
        
        # 2. Check lock
        br=0
        for i in range(M-1,N+M-1): # 2,3,4
            for j in range(M-1,N+M-1):
                if tmp[i][j] != 1:
                    br=1
                    break
            if br==1:
                chk=False
                break
            chk=True
        
        if (chk==True): 
            break       # while break
        elif (r_w==N+M-2) and (c_w==N+M-2):
            break       #while break
        elif (c_w==N+M-2):
            c_w=0       # while loop, initialize weight of col to 0
            r_w+=1      # plus 1 to weight of row
        else:   
            c_w+=1      # while loop, plus 1 to weight of col
    return chk

---

하지만 테스트케이스는 통과하였지만 채점을 했을때 런타임오류가 많이 떠서 점수는 40/100 이 되었다.

어디서 틀린건지는 잘 못찾겠다.

참고한 블로그

https://wonillism.github.io/programmers/Programmers-lock-and-key/

https://jay-ji.tistory.com/41