구현
프로그래머스 2020 KAKAO BLIND RECRUITMENT Level 3 문제 자물쇠와 열쇠를 Java를 이용해 풀어보았다.
결국 내 힘으로 못 풀었다. 그냥 너무 막막해서.. 오또케를 외치다가 머릿속에 드는 논리는 있지만 코드로 옮기지를 못했다.
그냥 힘으로 푸는 느낌의 문제다.
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/60059
배열 회전시키기
일단 주어진 배열 하나와 90도, 180도 그리고 270도 돌린 배열을 얻어내야 한다. 이를 위해서 int[][] rotateKey(int[][] src) 메소드를 선언했다. 이건 간단하다. 그냥 돌리면 된다.
static int[][] rotateKey(int[][] src){
int n = src.length;
int[][] res = new int[n][n];
int r=0,c=0;
for(int col=0; col<n; col++) {
for(int row=n-1; row>=0; row--){
res[r][c] = src[row][col];
c++;
}
r++; c=0;
}
return res;
}확장된 자물쇠 배열 선언하기
여기부터가 문제다. 키 네 가지 버전을 구하는 건 간단한데 자물쇠랑 이 키들을 겹쳐서 맞는 조합인지 찾는 게 코드로 옮기기가 좀 막막했다.
질문 목록에서 확장된 자물쇠 배열이라는 키워드를 얻어서 풀었다.
그림으로 보면 위와 같다. 원래 자물쇠 배열을 중앙에 두고 열쇠 배열을 최소한으로 겹치게 했을 때의 상태를 보면 위와 같다.
그래서 저 크기만큼의 새로운 자물쇠 배열을 얻어내서 네 가지 키랑 조합을 맞춰보면 된다.
이 새로운 확장된 자물쇠 배열은 다음과 같이 선언해주자.
int extension = key.length-1;
int[][] extendedLock = new int[lock.length + 2*extension][lock.length + 2*extension];확장된 자물쇠 배열 세팅하기
그럼 일단 확장된 자물쇠 배열 extendedLock은 다 0으로 초기화돼있으니 원래 자물쇠 배열 값을 넣어줘야 한다. 이는 다음과 같이 할 수 있다.
for(int r=0; r<lock.length; r++){ // 확장된 자물쇠 만들기
for(int c=0; c<lock.length; c++){
extendedLock[r+extension][c+extension] = lock[r][c];
}
}나중에 보겠지만 위의 이중 for문은 더 큰 5중 for문의 일부일 뿐이다. 나중에 확인하자.
그럼 이렇게 기존의 자물쇠 값은 넣어줬는데 여기에 key 배열의 값까지 추가해줘야 한다.
이는 어디서부터 겹쳤는지에 따라 작업이 달라지기 때문에 겹치기 시작한 지점의 좌표를 parameter 로 넘겨줘야 한다.
void setExtendedLock(int r, int c, int[][] key) 메소드를 선언해서 이 작업을 수행해줬다. parameter로 넘겨주는 r과 c가 겹치기 시작하는 지점이다.
static void setExtendedLock(int r, int c, int[][] key){
int len = key.length;
for(int i=0; i<len; i++)
for(int j=0; j<len; j++)
extendedLock[r+i][c+j] += key[i][j];
}이렇게 확장된 자물쇠 배열 extendedLock 세팅까지 마쳤다.
겹치는 지점 이동해가며 가능한 모든 경우 다 살펴보기
결국 원래 자물쇠 배열의 크기가 3*3 이면 키 배열과 겹치기 시작하는 지점이 (0,0) 부터 (2,2) 까지 돌아가며 다 위에서 했던 작업들을 반복해줘야 한다.
추가로 키도 네 가지 버전이 있기 때문에 이것까지 추가해주면 가장 바깥에 기본 3중 for문이 위치하고 있고 그 안에 위에서 살펴봤던 작업들을 추가해줘야 하는 것이다. 존나 반복 개쩐다!!! 씨방!!!
내가 어디에 있는지 정신 똑띠 차리고 봐야한다.
어쨌든 이걸 코드로 표현하면 다음과 같다.
for(int i=0; i<lock.length+extension; i++){ // 겹치는 부분 처리
for(int j=0; j<lock.length+extension; j++){ // 겹치는 부분 처리
for(int k=0; k<4; k++){ // key 종류 네 개
for(int r=0; r<lock.length; r++){ // 확장된 자물쇠 만들기
for(int c=0; c<lock.length; c++){
extendedLock[r+extension][c+extension] = lock[r][c];
}
}
setExtendedLock(i,j,keys[k]);
if(isOpen(extendedLock, extension, lock.length)) return true;
}
}
}많다~^^ ㅆ...
위의 모든 작업을 다 합친 코드는 아래와 같다. 내가 제출한 코드다.
public class LockAndKey {
static int[][][] keys = new int[4][][];
static int[][] extendedLock;
static boolean solution(int[][] key, int[][] lock) {
keys[0] = key;
keys[1] = rotateKey(key);
keys[2] = rotateKey(keys[1]);
keys[3] = rotateKey(keys[2]);
int extension = key.length-1;
extendedLock = new int[lock.length + 2*extension][lock.length + 2*extension];
for(int i=0; i<lock.length+extension; i++){ // 겹치는 부분 처리
for(int j=0; j<lock.length+extension; j++){ // 겹치는 부분 처리
for(int k=0; k<4; k++){ // key 종류 네 개
for(int r=0; r<lock.length; r++){ // 확장된 자물쇠 만들기
for(int c=0; c<lock.length; c++){
extendedLock[r+extension][c+extension] = lock[r][c];
}
}
setExtendedLock(i,j,keys[k]);
if(isOpen(extendedLock, extension, lock.length)) return true;
}
}
}
return false;
}
static int[][] rotateKey(int[][] src){
int n = src.length;
int[][] res = new int[n][n];
int r=0,c=0;
for(int col=0; col<n; col++) {
for(int row=n-1; row>=0; row--){
res[r][c] = src[row][col];
c++;
}
r++; c=0;
}
return res;
}
static void setExtendedLock(int r, int c, int[][] key){
int len = key.length;
for(int i=0; i<len; i++)
for(int j=0; j<len; j++)
extendedLock[r+i][c+j] += key[i][j];
}
static Boolean isOpen(int[][] map, int ext, int len){
for(int i=0; i<len; i++)
for(int j=0; j<len; j++)
if(map[i+ext][j+ext] != 1) return false;
return true;
}
public static void main(String[] args) {
int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
System.out.println(solution(key, lock));
}
}오늘 배운 것
복잡해도 정신 똑띠 차리고 힘으로 욱여 풀어보자
2022.03.10 재시도 ( 실패 )
역시 구현이 아주 숨 막히는 문제다. 이전에 푼 기억이 살짝 남아있어서 확장된 lock 배열을 만들어주는 것까지는 했는데, 겹쳐있는 부분에 대해서 어떻게 처리해야 할지를 해결하지 못해서 결국 또 못 풀었다. 이전에 풀었던 풀이를 살짝 보니 그렇게 복잡하지는 않은 것 같은데 막상 혼자 풀어보려 하면 참 어려운 게 구현인 것 같다..
아래는 다시 푼 풀이다.
import java.util.ArrayList;
class LockAndKey{
static int[][] extended_lock;
static ArrayList<int[][]> totalKeys = new ArrayList<>();
static int n,m;
static boolean solution(int[][] key, int[][] lock){
n = lock.length;
m = key.length;
int new_size = 3 * lock.length - 2;
extended_lock = new int[new_size][new_size];
createTotalKeys(key);
for(int r=0; r<2*n-1; r++){
for(int c=0; c<2*n-1; c++){
for(int[][] cur_key: totalKeys){
for(int n_r=0; n_r<n; n_r++){
for(int n_c=0; n_c<n; n_c++){
extended_lock[n_r+n-1][n_c+n-1] = lock[n_r][n_c];
}
}
if(overlap(cur_key, r, c)) return true;
}
}
}
return false;
}
static boolean overlap(int[][] key, int r, int c){
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
extended_lock[r+i][c+j] += key[i][j];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(extended_lock[n+i-1][n+j-1]!=1) return false;
return true;
}
static void createTotalKeys(int[][] org){
totalKeys.add(org);
totalKeys.add(rotateKey(totalKeys.get(totalKeys.size()-1)));
totalKeys.add(rotateKey(totalKeys.get(totalKeys.size()-1)));
totalKeys.add(rotateKey(totalKeys.get(totalKeys.size()-1)));
}
static int[][] rotateKey(int[][] key){
int[][] r90 = new int[m][m];
for(int r=0; r<m; r++)
for(int c=0; c<m; c++)
r90[r][c] = key[m-1-c][r];
return r90;
}
public static void main(String[] args) {
int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
boolean res = solution(key, lock);
System.out.println(res);
}
}5중 for문 토 나온다.....
