자물쇠와 열쇠

유승선 ·2022년 2월 16일
0

프로그래머스

목록 보기
16/48


예전부터 너무 풀고싶었던 자물쇠와 열쇠 문제이다. 2020 카카오 코딩테스트에서 나왔던 구현문제로서 특수 알고리즘을 쓰는것보다는 완전탐색에 집중해서 얼마나 구현을 잘 할수있냐의 중점을 둔 문제같다. 지금까지 꽤 많은 구현 문제를 풀긴 풀었지만 아직도 너무 헷갈린게 이렇게 도형을 사용한 문제가 나오면은 머리가 하얘져서 이 문제를 해결함에 있어서 많은 참고자료들이 필요했고 공부또한 많이 해서 내 코드로 순화 시켰다.

나중에 이런 비슷한 문제를 볼지 모르겠지만. 도형을 이용한 완전탐색에 있어서 필요한거는 원래 쓰려고 하는 도형보다 훨씬 더 큰 판을 사용하는것이다. 그 판 안에서 key 와 lock의 모든조합을 구현 하는게 포인트. 그런데 이런 구상을 코드로 옮기는게 여간 어려운게 아니기때문에 하나하나 전부 다 공부해봤다.

가장 첫번째로 lock 사이즈에 3배만큼인 matrix 벡터를 만들어주었다. 그리고 lock을 가운대로옮기는 과정에서 matrix 사이즈 - lock 사이즈만큼 해서 시작점과 끝을 지정해주었다.

key를 90도씩 회전해서270도를 rotate 할 생각으로 k < 4 라는 룹을 만들어주었다. 그리고 혹시라도 원래 가지고 있는 key가 lock을 열수도 있기때문에 rotate를 룹이 끝나는 마지막에 넣어주었다. check함수는 지정된 포인트 i와 j에서 도형의 크기만큼 lock의 흠 부분과 맞는지 확인을 해주기 위해서 넣은거고 true가 리턴되면 lock 값이 전부다 1이 된 상태기 때문에 답을 바로 리턴했다. 만약에 답이 아니라면 조정된 matrix를 원래 값으로 바꾸었다.

전에 풀었던 leetcode 문제에서 얻은 가장 깔끔한 matrix 회전 방법을 응용해봤다

가장 헷갈렸던? 부분이 아닐까 싶다. 그런데 생각해보면 되게 간단한 코드이다. 이전에 x 와 y 포인트를 받게되면 key의 크기만큼만 늘려서 완전탐색을 해야하기 때문에 x + M 그리고 y + M이 쓰였다. 그리고 += key[i-x][j-y] 를 해준 이유는 matrix안에 key값을 더해줌으로써 lock안에 있는 흠이 모두 채워져있는지를 확인 할수있어서이다. 개인적으로 색다롭고 좋다 생각했던 방법중에 하나인거같다. i-x가 되게헷갈렸는데 생각해보니 꽤간단했던것.

더해주는 과정을 끝내고 난 뒤에는 다시 matrix를 오리지널로 돌려야하기때문에 이 전에 썼던 코드와 마찬가지로 포인틀를 설정해주고 다시 초기화를 시켰다.

배운점:
1. Matrix를 회전시키는 방법, 그리고 응용
2. i와j를 사용한 알맞는 matrix 탐색방법
3. 도형을 이용한 완전탐색 과정

profile
성장하는 사람

0개의 댓글