2020 카카오 1차 코딩테스트 - 자물쇠와 열쇠 c++

링크

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

해결시간 : 약 1시간 40분

2차원 배열(c++의 경우는 2차원 int형 벡터)를 조작하면서 열쇠를 자물쇠에 갖다대는 작업을 하면 되는 브루트포스 문제였다.

크기가 애초에 20*20밖에 안되기 때문에 브루트포스로 가능.

 

우선 첫번째 해야할 과정은 key를 시계방향으로 돌리는 작업이다.

이 과정은 그림을 그려보고 대응되는 인덱스들을 차근차근 따져보면 충분히 단시간에 할 수 있었다.

두번째로 해결해야 하는 과정은 자물쇠에 열쇠를 갖다대는 작업.. 나는 총 경우의 수가 어느정도가 되는지 궁금해서

열쇠 3*3, 자물쇠 4*4 크기라고 가정하고 문제에 접근해 보았다.

알아낸건 총(N+M-1)^2의 경우의 수가 생긴다는 것.

문제는 그 구현이었는데, 밑의 try1은 내가 처음에 하려다가 어려움을 느낀 부분을 적어놓았다.

부분부분을 lock자체에다가 더하려고 시도했는데, 어떻게 넣어야될지 규칙이라던지 아이디어가 떠오르지 않아서 시간을 많이 소비했다.

try2에서 더 쉬운 방식을 알아내게 되었고, 이 방식대로 문제를 풀었더니 쉽게 풀 수 있었다.

 

문제를 풀고 느낀점

1. 반드시 내가 구현할 수 있는 범위 내에서 문제를 풀 수 있게 나온다. 다만 더 쉽게 풀어낼 수 있는 아이디어를 생각해내야 한다. 

 

코드

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int M = key.size();
    int N = lock.size();
    for(int time=0;time<4;time++){
        //시계방향으로 네번 돌려서 테스트를 해보는거다.
        //newkey 초기화
        vector<vector<int>> newkey(M,vector<int>(M,0));
 
        for(int i=0;i<M;i++)
            for(int j=0; j<M;j++)
                newkey[j][M-1-i]=key[i][j];
//        for(int i=0;i<M;i++)
//            for(int j=0; j<M;j++)
//                cout<<newkey[i][j];
        //원래키 업데이트
        for(int i=0;i<M;i++)
            for(int j=0; j<M;j++)
                key[i][j]=newkey[i][j];
 
        //이제 자물쇠랑 열쇠를 맞춰보는 작업을 해야한다. 근데 어떡해야 하징?
        //총 경우의 수는 (N+M-1)^2의 경우의 수가 생긴다.
        for(int i=0; i<N+M-1; i++){
            for(int j=0; j<N+M-1; j++) {
 
                //큰 자물쇠 newlock 초기화
                vector<vector<int>> newlock(2 * M - 2 + N, vector<int>(2 * M - 2 + N, 0));
 
                for (int ii = 0; ii < N; ii++)
                {
                    for (int jj = 0; jj < N; jj++)
                    {
                    newlock[ii + M - 1][jj + M - 1] = lock[ii][jj];
                    }
                }
 
 
                //newlock이랑 newkey 합치기
                for(int ii=0; ii<M; ii++) {
                    for (int jj = 0; jj < M; jj++) {
                        newlock[ii + i][jj + j] += newkey[ii][jj];
                    }
                }
 
                //newlock의 가운데부분 보기. 이제 맞나 안맞나를 판단하는거다.
                int count=0;
                for(int ii=M-1;ii<M+N-1;ii++){
                    for(int jj=M-1;jj<M+N-1;jj++){
                        if(newlock[ii][jj]==1){
                            count++;
                        }
                    }
                }
                if(count==N*N) {
                    
                    return true;
                }
 
            }
        }
 
    }
    return false;
}