[카카오 코딩 테스트] 좌물쇠와 열쇠

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설 – tech.kakao.com

3번 자물쇠와 열쇠 문제입니다.

은근 머리가 복잡해지는 문제였습니다. 단순히 생각하면 다 해보면 되는 문제지만.. 

2D array를 90도 회전시키고 옆으로 아래로 이동시키는 부분들이 한군데만 오류가 있어도 찾기가 힘들어서 

실제 시험이었다면 저는 시간상 패스했을 것 같습니다.

 

풀이 과정은 아래 두가지만 하면 됩니다.

1) 총 4번 반복(90도씩 회전)

2) Lock의 3배가 되는 배열을 생성하고 Lock을 센터에 위치. key를 한칸씩 옮기면서 맞는지 체크

  (key가 Lock을 벗어나도 되기 때문에 이를 고려하기 위해 3배 배열 생성)

 

하지만 2번이 은근.. 생각보다 힘들었네요 ㅠㅠ

 

아래는 풀이한 코드입니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
void rotate(vector<vector<int>> &key) {
    int n = key.size();
    vector<vector<int>> tmp(n,vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tmp[i][j] = key[n - 1 - j][i];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            key[i][j] = tmp[i][j];
        }
    }
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int m = key.size();
    int n = lock.size();
    for (int i = 0; i < 4; i++) {        
        int zero_cnt = 0;
        // 3배의 배열을 만들고 lock을 가운데 세팅
        vector<vector<int>> tmp(3 * n, vector<int>(3 * n));
        for (int j = n; j < n + n; j++) {
            for (int z = n; z < n + n; z++) {
                tmp[j][z] = lock[j-n][z-n];
                if (lock[j-n][z-n] == 0) zero_cnt++;
            }
        }
        // 이동시킬 key의 복제
        vector<vector<int>> tmp_key(m, vector<int>(m));
        for (int j = 0; j < m; j++) {
            for (int z = 0; z < m; z++) {
                tmp_key[j][z] = key[j][z];
            }
        }
        // 한칸씩 오른쪽, 아래로 옮기며 모든 경우 테스트
        for (int x = 0; x < 2 * n; x++) {
            for (int y = 0; y < 2 * n; y++) {
                int correct_cnt = 0;
                bool incorrect = false;
                // 맞는지 확인
                for (int j = 0; j < m; j++) {
                    for (int z = 0; z < m; z++) {
                        if (tmp_key[j][z] == 1 && tmp[j + x][z + y] == 0) {
                            // key는 돌기, lock은 홈 부분, 
                            // 그리고 그 좌표가 lock에 해당할때 맞는 개수 + 1 
                            if ((j + x >= n) && (j + x < 2 * n) 
                                && (z + y >= n) && (z + y < 2 * n))
                                correct_cnt++;
                        }
                        // 둘다 돌기일때는 무조건 false!
                        else if (tmp_key[j][z] == 1 && tmp[j + x][z + y] == 1) {
                            incorrect = true;
                            break;
                        }
                    }
                    if (incorrect) break;
                }
                // 맞는 개수와 lock의 전체 홈 부분의 수가 같으면 true
                if (zero_cnt == correct_cnt && !incorrect) {
                    return true;
                }
            }
        }
        // 회전
        rotate(key);
    }
    
    return answer;
}
int main() {
    vector<vector<int>> key = { { 0, 0, 0 }, { 1, 0, 0 }, { 0, 1, 1 } };
    vector<vector<int>> lock = { { 1, 1, 1 }, { 1, 1, 0 },{ 1, 0, 1 } };
 
    cout << solution(key, lock);
    return 0;
}