[프로그래머스, C++]자물쇠와 열쇠(2020 카카오 블라인드 채용)

문제 링크

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

 

 

풀이

검색으로 "완전 탐색"이라는 힌트를 얻고 풀었다.

컴퓨터 비전 강의를 수강해서 그런지 zero-pedding으로 구현하여 메모리는 좀 더 쓰고 비교 구문들을 제거했다.

 

// 요약

// 함수들

1) rotate_90() 함수: 시계 방향으로 90도를 돌리는 함수 --- 정방형 배열이므로 저런 규칙이 나왔다, 실제로 돌려본...

2) check() 함수: zero-pedding을 했지만 안쪽만 모두 홈이 채워졌는지 검사

3) compare_xor() 함수: 문제 조건에 돌기와 돌기는 부딪히면 안되므로 서로 다른 값이여야 1이 되는 배타적 논리합을 사용하였다.

4) solution() 함수: 문제 풀이 함수

lock을 zero-pedding으로 늘려주고 key를 0, 90, 180, 270도로 돌리면서 key를 check() 하였다.

여기서 주의할 점은 zero-pedding으로 늘려준 사이즈만큼 반복문을 돌리는 것이 아닌 key가 lock과 겹치는 구간 동안만 돌리게 해야한다.(안그러면 segment fault 예상)

 

#include <string>
#include <vector>

using namespace std;

void rotate_90(vector<vector<int>>& key){
    vector<vector<int>> temp(key);
    int keySize = key.size();
    for(int i=0; i<keySize; i++){
        for(int j=0; j<keySize; j++){
            key[j][keySize-1-i] = temp[i][j];
        }
    }
}

bool check(vector<vector<int>>& lock, int start, int end){
    for(int i=start; i<end; i++){
        for(int j=start; j<end; j++){
            if(lock[i][j]==0){
                return false;
            }
        }
    }
    return true;
}

void compare_xor(vector<vector<int>>& lock, vector<vector<int>>& key, int x, int y){
    for(int i=0; i<key.size(); i++){
        for(int j=0; j<key.size(); j++){
            lock[x+i][y+j] ^=  key[i][j];
        }
    }
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keySize = key.size();
    int lockSize = lock.size();
    
    vector<int> zero(lockSize, 0);
    lock.insert(lock.begin(), keySize-1, zero);
    lock.insert(lock.end(), keySize-1, zero);
    for(int i=0; i<lockSize+(keySize-1)*2; i++){
        lock[i].insert(lock[i].begin(), keySize-1, 0);
        lock[i].insert(lock[i].end(), keySize-1, 0);
    }
    
    for(int i=0; i<lockSize+keySize-1; i++){
        for(int j=0; j<lockSize+keySize-1; j++){
            for(int four=0; four<4; four++){
                vector<vector<int>> temp(lock);
                compare_xor(temp, key, i, j);
                if(check(temp, keySize-1, keySize-1+lockSize)) return true;
                rotate_90(key);
            }
        }
    }
    return false;
}