[KAKAO] 자물쇠와 열쇠 (2020 KAKAO BLIND)

몇 주전에 이 문제를 봤을 때 브루트포스 인걸 알았지만, 탐색할 때 백트래킹으로 해야한다고 생각했다.

그래서 삼성 SW 기출문제를 몇 개 풀어보고 최근에 다시 와서 봤다. 문제를 보자마자 아무 생각 없이 백트래킹으로 짜봤는데.. 

아직 실력이 부족한 지 시간초과가 계속 뜨긴 했다.

이유는 디버깅을 통해 알았지만, 디버깅을 하면서 이 문제를 백트래킹이 아닌 이중 포문으로 탐색해도 될 것 같다는 느낌이 들었다.

 

문제를 풀 때마다 느끼는건 어떻게 문제를 접근하냐에 따라서 잘못된 방향으로 빠져버리면 시간을 엄청 잡아먹는다.

어찌보면 수능 수학,과학과 비슷하게 느껴질 순 있다.. 저 시기를 뒤돌아 봤을 때 많은 문제를 푸는것 만큼 좋은게 없던 것 같다.

몰랐던 부분들을 하나 둘, 오답노트를 만들어가며 부족한 것을 메꿔 갔던 것 같다.

블로그로 이런 부족한 부분들을 메꿔 나가면 비슷하게 좋은 결과가 있지 않을까..? 라는 생각이 든다 ㅋ.ㅋ

 

항상 문제를 풀 때마다 부족함을 느끼고 있고, 문제에 접근 조차 하지 못할 때는 좌절감을 맛보지만 오히려 자극이 되는것 같다.

스스로 뭐가 부족한지 아는게 중요하다고 생각한다. (나는 dp, greedy, 백트래킹) 

 

programmers.co.kr/learn/courses/30/lessons/60059?language=python3

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

문제를 딱 봤을 때 2가지 생각이 들었다.

1. 행렬을 어떻게 90도 회전하지...?

 

2. 탐색은 어떻게 해야할까?

 

처음 문제를 봤을 때 90도 회전해야한다는 생각에 몇 번 생각도 안 해보다가 뒤로가기 버튼 눌렀던게 생각난다...

제일 큰 이유는 2번때문이긴 했으나 종이에 적으면서 규칙이나 찾아보니 금방 눈에 들어왔다.

 

90도 시계방향 회전

묶음으로 표시 해놨던 것을 자세히 보면 규칙을 알 수 있다.

탐색을 7, 4, 1, 8, 5, 2... 이런식으로 제일 N 행에서 첫 행까지 N개의 열을 반복하면 된다.

 

탐색은 어떤식으로 해야할까..

계속 생각하다가 key의 첫 좌표를 기준으로 한 번 해보자 해서 생각해낸 것이 다음과 같다.

 

그림이 생각보다 별로 이쁘지 않은것 같지만..

key의 길이를 n 이고 lock의 길이를 N, 첫 좌표를 (0, 0) 이라 해보자.

key의 첫 좌표는 (-n+1, -n+1) 부터 (N-1, N-1) 가능 하다고 볼 수 있다. 이렇게 모든 방법을 고려해 코드를 짤 수 있다.

 

tip)

is_ok() 함수를 보면  -> if ok[i][j] == 0 or ok[i][j] == 2:  부분을 볼 수 있다. 이 이유는 키가 홈이난 부분하고 딱 정확히 맞아야 함으로

모든 ok[i][j] 의 값이 1이되어야 함을 나타내는 것과 같다.

 

 

from copy import deepcopy

answer = False

def solution(key, lock):
    lock_N, key_N = len(lock), len(key)

    def rotate_90():
        new_key = [[0 for j in range(key_N)] for i in range(key_N)]
        for i in range(key_N):
            for j in range(key_N-1, -1, -1):
                new_key[i][abs(j-(key_N-1)) % key_N] = key[j][i]
        return new_key

    def is_ok(r, c):
        global answer
        ok = deepcopy(lock)
        for i in range(key_N):
            for j in range(key_N):
                if 0 <= i+r < lock_N and 0 <= j+c < lock_N:
                    ok[i+r][j+c] += key[i][j]

        for i in range(lock_N):
            for j in range(lock_N):
                if ok[i][j] == 0 or ok[i][j] == 2:
                    return False
        answer = True
        return
    
    for i in range(-key_N+1, lock_N):
        if answer == True: break
        for j in range(-key_N+1, lock_N):
            if answer == True: break
            for k in range(4):
                key = deepcopy(rotate_90())
                is_ok(i, j)

    return answer