[프로그래머스] 자물쇠와 열쇠

2020 카카오 블라인드 채용 코딩 테스트 문제입니다.

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

문제 확인

 

구현, 완전 탐색 문제입니다.

 

풀이

 

초기 자물쇠 lock의 홈의 개수를 저장해 둡니다.

매번 확인 시 배열을 회전하지 말고 처음에 key 배열을 회전하여 따로 저장합니다. 이를 통해 메모리 검색 시간과 회전 비용을 줄일 수 있습니다.

완전 탐색 범위는 초기 위치 (i, j) : 1 - key.size() ~ n, 배열 조건 검사 위치 (ki, kj) : 0 ~ m까지 탐색하게 됩니다.

이로 인하여 비교할 값은 lock[i + ki][j + kj], key [ki][kj]가 됩니다.

1. lx, ly가 0~n-1을 만족하지 않으면 어떠한 경우라도 조건을 위해하지 않으므로 넘어갑니다.
2. lock[lx][ly] == 0 && key[ki][kj] == 1 : 자물쇠의 홈, 열쇠의 돌기가 맞아떨어져 count++
3. lock[lx][ly == key[ki][kj] : 이 경우 모두 0 이면 자물쇠의 일부 홈이 맞춰지지 않아 열 수 없으며, 모두 1인 경우 돌기와 돌기가 만나 맞춰지지 않으므로 두 경우 모두 일찍 종료합니다.
4. 남은 경우의수 lock[lx][ly] == 1 && key[ki][kj] == 0의 경우 조건을 위배하지 않으므로 넘어갑니다.

배열 조건 검사가 끝이 나면 탐색한 범위 외부에 맞춰야 할 홈이 있는 경우가 있으므로 "count == 전체 홈의 개수"를 만족하면 true를 반환합니다.

이러한 과정을 회전한 4개의 배열과 모두 비교합니다.

 

코드

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int n = lock.size(), m = key.size();
 
    int zero_cnt = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!lock[i][j])
                ++zero_cnt;//맞춰야 할 홈의 개수 저장
 
    int key_90[20][20], key_180[20][20], key_270[20][20];
 
    for (int i = 0; i < m; i++)//배열 회전
        for (int j = 0; j < m; j++) {
            key_270[m - 1 - j][i] = key_180[m - 1 - i][m - 1 - j] = key_90[j][m - 1 - i] = key[i][j];
        }
 
 
    for (int i = 1 - m; i < n; i++) {
        for (int j = 1 - m; j < n; j++) {
            int lx, ly;
            int cnt = 0;
            for (int ki = 0; cnt != -1 && ki < m; ki++) {
                lx = i + ki;
                if (lx < 0 || n <= lx) continue;
                for (int kj = 0; kj < m; kj++) {
                    ly = j + kj;
                    if (ly < 0 || n <= ly)continue;//범위 밖
                    if (lock[lx][ly] == 0 && key[ki][kj] == 1)++cnt;//홈과 돌기가 맞음
                    else if (lock[lx][ly] == key[ki][kj]) { cnt = -1; break; }//0 : 일부 홈이 맞지 않음, 1 : 돌기, 돌기
                }
            }
            if (cnt == zero_cnt) return true;//맞춰야 할 홈의 개수가 맞으면 종료
 
            cnt = 0;
            for (int ki = 0; cnt != -1 && ki < m; ki++) {//90도
                lx = i + ki;
                if (lx < 0 || n <= lx) continue;
                for (int kj = 0; kj < m; kj++) {
                    ly = j + kj;
                    if (ly < 0 || n <= ly)continue;
                    if (lock[lx][ly] == 0 && key_90[ki][kj] == 1)++cnt;
                    else if (lock[lx][ly] == key_90[ki][kj]) { cnt = -1; break; }
                }
            }
            if (cnt == zero_cnt) return true;
 
            cnt = 0;
            for (int ki = 0; cnt != -1 && ki < m; ki++) {//180도
                lx = i + ki;
                if (lx < 0 || n <= lx) continue;
                for (int kj = 0; kj < m; kj++) {
                    ly = j + kj;
                    if (ly < 0 || n <= ly)continue;
                    if (lock[lx][ly] == 0 && key_180[ki][kj] == 1)++cnt;
                    else if (lock[lx][ly] == key_180[ki][kj]) { cnt = -1; break; }
                }
            }
            if (cnt == zero_cnt) return true;
 
            cnt = 0;
            for (int ki = 0; cnt != -1 && ki < m; ki++) {//270도
                lx = i + ki;
                if (lx < 0 || n <= lx) continue;
                for (int kj = 0; kj < m; kj++) {
                    ly = j + kj;
                    if (ly < 0 || n <= ly)continue;
                    if (lock[lx][ly] == 0 && key_270[ki][kj] == 1)++cnt;
                    else if (lock[lx][ly] == key_270[ki][kj]) { cnt = -1; break; }
                }
            }
            if (cnt == zero_cnt) return true;
 
        }
    }
 
    return false;
}
 
int main() {
    vector<vector<int>>lock = { { 1} };
    vector<vector<int>>key = { {1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0} };
    cout << solution(key, lock);
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.96MB)
테스트 2 〉	통과 (0.01ms, 3.97MB)
테스트 3 〉	통과 (0.04ms, 3.9MB)
테스트 4 〉	통과 (0.02ms, 3.97MB)
테스트 5 〉	통과 (0.02ms, 3.96MB)
테스트 6 〉	통과 (0.01ms, 3.84MB)
테스트 7 〉	통과 (0.05ms, 3.96MB)
테스트 8 〉	통과 (0.09ms, 3.98MB)
테스트 9 〉	통과 (0.03ms, 3.96MB)
테스트 10 〉	통과 (0.05ms, 3.96MB)
테스트 11 〉	통과 (0.10ms, 3.97MB)
테스트 12 〉	통과 (0.01ms, 3.96MB)
테스트 13 〉	통과 (0.03ms, 3.97MB)
테스트 14 〉	통과 (0.02ms, 3.97MB)
테스트 15 〉	통과 (0.02ms, 3.97MB)
테스트 16 〉	통과 (0.04ms, 3.96MB)
테스트 17 〉	통과 (0.02ms, 3.75MB)
테스트 18 〉	통과 (0.04ms, 3.97MB)
테스트 19 〉	통과 (0.01ms, 3.97MB)
테스트 20 〉	통과 (0.06ms, 3.92MB)
테스트 21 〉	통과 (0.06ms, 3.96MB)
테스트 22 〉	통과 (0.04ms, 3.96MB)
테스트 23 〉	통과 (0.02ms, 3.91MB)
테스트 24 〉	통과 (0.03ms, 3.97MB)
테스트 25 〉	통과 (0.06ms, 3.84MB)
테스트 26 〉	통과 (0.11ms, 3.79MB)
테스트 27 〉	통과 (0.13ms, 3.96MB)
테스트 28 〉	통과 (0.04ms, 3.96MB)
테스트 29 〉	통과 (0.03ms, 3.95MB)
테스트 30 〉	통과 (0.05ms, 3.96MB)
테스트 31 〉	통과 (0.04ms, 3.93MB)
테스트 32 〉	통과 (0.10ms, 3.96MB)
테스트 33 〉	통과 (0.06ms, 3.95MB)
테스트 34 〉	통과 (0.01ms, 3.96MB)
테스트 35 〉	통과 (0.02ms, 3.96MB)
테스트 36 〉	통과 (0.02ms, 3.73MB)
테스트 37 〉	통과 (0.02ms, 3.92MB)
테스트 38 〉	통과 (0.01ms, 3.98MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0