[프로그래머스] 자물쇠와 열쇠 / 2020_카카오_공채 [C++][lv.3]

 

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

프로그래머스

#문제 간단 정리

 

2차원 배열을 이용하여 자물쇠와 키를 대조하여 정답을 찾자.

다만 키가 자물쇠의 영역을 벗어나는 것이 주목 포인트다

 

 

 

#문제 해결 방법

일단 대략적인 내용은 문제를 읽어서 이해했다고 치고

큰 문제 해결의 맥락을 잡으면

1. 키와 자물쇠를 2차원 배열을 이용해서 표시한다.

2. 그렇게 받은 키의 회전 함수를 구현한다. (하나씩 대조하면서 좌표가 어떻게 변하는지 확인하자)

3. 키를 자물쇠에 넣어서 확인한다.

 

이 문제에서는 3번이 핵심이 된다.

우선 처음에는 방법 두어가지가 떠오르는데.

3-1. 자물쇠에 넣을 키의좌표를 유동적으로 넣어가면서 검사.

3-2.  자물쇠를 연장시켜서 자물쇠*3의 맵을 만들어 키를 넣어가면서 검사.

 

우선 1번이 좀 더 고급진 방법이겠지만

구현문제이기 때문에 가장 구현이 쉽고 간단할 3-2번 방법으로 선택

그림으로 표현하자면  대략 다음과 같다

자물쇠를 *3 하여 연장

그림을 보면  나는  n(자물쇠)*3 로 구현을 했지만 키가 완전히 맵과 안겹치는건 쓸모가 없기 때문에 한칸 줄여서 맵을 만들면 좀 더 속도가 빨라졌을 것이다.

 

이후 내가 푸는 방법은

자물쇠의 0의 개수를 세준다음

연장한 자물쇠는 모두 2로 채워준다

그리고 키를 첫번째 칸부터 마지막 칸까지 이동시키면서 대조한후

회전시킨후 반복을 3번 더 시켜준다 (360도)

그림으로 보이자면 대략 이렇다

키를 대입한 연장 자물쇠

만약 대조하면서 키가 1 자물쇠가 0 라면 정답 카운트 +1

자물쇠가 1 키가 1 이면 정답 카운트를 -123456789로 설정하여 오답처리

자물쇠가 0 키가 0 이여도 오답처리

 

정답카운트가 자물쇠의 빈 공간 카운트와 일치한다면

정답을 찾은것이다.

 

사실 여기서 자물쇠의 키의값을 더해서 정답을 찾아도 좋을 것 같고.

우선 주어진 맵의 길이가 20정도로 작기 때문에 연장후 회전까지 한 테스트 케이스가

생각보다 작기 때문에 단순한 맵 연장이 가장 좋을 것 같다는 생각이 들었다.

(단순하고 틀리기 가장 어려우니까)

 

 

 

#전체 코드

 

#include <string>
#include <vector>
#include <iostream>
int n,m;


using namespace std;

vector<vector<int>> rotate(vector<vector<int>> key){ // key 시계방향 90도 회전
    vector<vector<int>> tmp;
    tmp.resize(n,vector<int>(n,0));
    
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            tmp[i][j] = key[m-1-j][i];
        }
    }
    return tmp;
}



int match(){
    
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    bool answer = false;
    m = key[0].size(); n = lock[0].size();

    vector<vector<int>> newMap;
    newMap.resize(n*3,vector<int>(n*3,2)); // 확장된 자물쇠 m*3의 크기
    
    
    int countEmpty = 0;
    cout << "map: \n";
    for(int i=0;i<n;i++){ //lock 의 빈 공간 카운트
        for(int j=0;j<n;j++){
            if(lock[i][j] == 0){
                countEmpty++;
            } 
            newMap[i+m][j+m] = lock[i][j]; //newMap 갱신
            cout << lock[i][j] <<" "; //map 출력
        }
        cout << "\n";
    }
    
    cout << "key: \n";
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cout << key[i][j] << " ";
        }
        cout << "\n";
    }
    
    cout << "emptyCount: " << countEmpty << "\n";

    for(int k=0; k<4; k++){
        if(k != 0) key = rotate(key);

    
    for(int i=0;i<m*3;i++){ //match 인지 확인하기
        for(int j=0;j<m*3;j++){
            
            //lock에 맞는지 확인하는 구간
            int ansCount = 0;
            for(int i2=0; i2<m; i2++){
                for(int j2=0; j2<m; j2++){
                    if(i2 + i < n*3 && j2 + j <n*3){ //범위 제한
                        
                    
                    if(newMap[i+i2][j+j2] == 0 && key[i2][j2] == 1 ){ 
                            ansCount++;
                    }  
                    if(newMap[i+i2][j+j2] == 0 && key[i2][j2] == 0){ 
                            ansCount = -123456789;
                    } 
                    if(newMap[i+i2][j+j2] == 1 && key[i2][j2] == 1){ 
                            ansCount = -123456789;
                    } 
                        
                    }//범위지정
                }   
            }
            cout << ansCount << " ";
             if(ansCount == countEmpty){
                        answer = true;
                }
        }
        
    } 
        
    } // 회전
    
    
    
    return answer;

}