[프로그래머스] 자물쇠와 열쇠 - 2020 카카오 신입 공채 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/60059?language=java

프로그래머스

---

문제

아이디어

문제를 해결하기 위해 아래와 같이 접근했다.

1. key 를 90도씩 4번 회전하며 반복
2. lock의 크기를 3배 확장 -> 범위 밖 계산을 용이하게 하기 위함
3. 확장된 lock 위치에서 key를 끼워 맞추기
4. 모든 lock의 홈이 채워지는지 체크
5. 모두 채워지면 true, 아니면 false

1. key를 90도씩 4번 회전하며 반복

: 주어진 정사각형 배열 key를 시계방향으로 90도 회전시킨다.

// 90도 회전 함수
static int[][] rotate(int[][] key) {
    int n = key.length;
    int[][] rotated = new int[n][n];

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            rotated[j][n-i-1] = key[i][j];
        }
    }
    return rotated;
}

 

2. lock의 크기를 3배 확장

: 기존 lock의 크기에서 3배를 확장시키면 그 위에서 key 배열이 이동하더라도 IndexOutOfBoundsException() 이 발생하지 않는다.

(조건에서 key의 크기는 M, lock의 크기는 N인데, M은 항상 N 이하라고 했으므로)

// 자물쇠 확장
int newSize = lockSize * 3;
int[][] extendedLock = new int[newSize][newSize];

// 중앙에 기존 lock 삽입
for(int i=0; i<lockSize; i++) {
    for(int j=0; j<lockSize; j++) {
        extendedLock[i + lockSize][j + lockSize] = lock[i][j];
    }
}

 

3. 확장된 lock 내에서 key 끼워 맞추기

: 확장된 lock (extendedLock) 의 위치에 key를 더해서 맞춰본다. key가 고정된게 아니라, 이동하는 것이므로 확장된 lock의 모든 x, y 좌표에 대해 key를 삽입해본다.

for(int x=0; x<newSize - keySize; x++) {
    for(int y=0; y<newSize - keySize; y++) {
        // key 삽입
        for(int i=0; i<keySize; i++) {
            for(int j=0; j<keySize; j++) {
                extendedLock[x+i][y+j] += key[i][j];
            }
        }
        
        ...
    }

 

4. 모든 lock의 홈이 채워지는지 체크

: check 함수를 이용하여 lock 배열이 모두 1이 되는지 확인한다. (이때 본래의 lock 배열은 extendedLock 배열의 중심에 위치해있음. 따라서, 아래 코드와 같이 extendedLock 중심으로부터 기존 lock 배열 크기만큼만 탐색)

static boolean check(int[][] extendedLock, int lockSize) {
    for(int i=lockSize; i<lockSize*2; i++) {
        for(int j=lockSize; j<lockSize*2; j++) {
            if(extendedLock[i][j] != 1)
                return false;
        }
    }

    return true;
}

for(int x=0; x<newSize - keySize; x++) {
    for(int y=0; y<newSize - keySize; y++) {
        // key 삽입
        for(int i=0; i<keySize; i++) {
            for(int j=0; j<keySize; j++) {
                extendedLock[x+i][y+j] += key[i][j];
            }
        }

        // key가 lock에 맞는지 확인
        if(check(extendedLock, lockSize)) {
            return true;
        }
        ...
    }

 

5. lock 배열이 모두 1이되면 true, 아니면 false 반환

: key가 lock과 맞지 않다면, 끼웠던 key 제거 후 1~4 과정 반복

for(int x=0; x<newSize - keySize; x++) {
    for(int y=0; y<newSize - keySize; y++) {
        // key 삽입
        for(int i=0; i<keySize; i++) {
            for(int j=0; j<keySize; j++) {
                extendedLock[x+i][y+j] += key[i][j];
            }
        }

        // key가 lock에 맞는지 확인
        if(check(extendedLock, lockSize)) {
            return true;
        }

        // key 제거
        for(int i=0; i<keySize; i++) {
            for(int j=0; j<keySize; j++) {
                extendedLock[x+i][y+j] -= key[i][j];
            }
        }
    }
}

---

전체 코드

// 90도 회전 함수
static int[][] rotate(int[][] key) {
    int n = key.length;
    int[][] rotated = new int[n][n];

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            rotated[j][n-i-1] = key[i][j];
        }
    }
    return rotated;
}

static boolean check(int[][] extendedLock, int lockSize) {
    for(int i=lockSize; i<lockSize*2; i++) {
        for(int j=lockSize; j<lockSize*2; j++) {
            if(extendedLock[i][j] != 1)
                return false;
        }
    }

    return true;
}

static boolean solution(int[][] key, int[][] lock) {
    int lockSize = lock.length;
    int keySize = key.length;

    // 자물쇠 확장
    int newSize = lockSize * 3;
    int[][] extendedLock = new int[newSize][newSize];

    // 중앙에 기존 lock 삽입
    for(int i=0; i<lockSize; i++) {
        for(int j=0; j<lockSize; j++) {
            extendedLock[i + lockSize][j + lockSize] = lock[i][j];
        }
    }

    // 90도씩 4번 회전
    for(int rot=0; rot<4; rot++) {
        key = rotate(key);

        for(int x=0; x<newSize - keySize; x++) {
            for(int y=0; y<newSize - keySize; y++) {
                // key 삽입
                for(int i=0; i<keySize; i++) {
                    for(int j=0; j<keySize; j++) {
                        extendedLock[x+i][y+j] += key[i][j];
                    }
                }

                // key가 lock에 맞는지 확인
                if(check(extendedLock, lockSize)) {
                    return true;
                }

                // key 제거
                for(int i=0; i<keySize; i++) {
                    for(int j=0; j<keySize; j++) {
                        extendedLock[x+i][y+j] -= key[i][j];
                    }
                }
            }
        }
    }
    return false;
}