알고리즘(C++) / 프로그래머스 level 3 : 자물쇠와 열쇠

level 3 : 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059?language=cpp 

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

 

코드

//프로그래머스 자물쇠와 열쇠
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <sstream>

using namespace std;

//시계방향 90도 회전
void rotation(vector<vector<int>>& key) {
    vector <vector<int>> key_rotation;
    for (int i = 0; i < key.size(); i++) {
        vector<int> temp;
        for (int j = 0; j < key.size(); j++) {
            temp.push_back(key[key.size() - j - 1][i]);
        }
        key_rotation.push_back(temp);
    }
    key = key_rotation;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    map<string, int> blank; //Lock에서 비워져있는 위치
    for (int i = 0; i < lock.size(); i++) {
        for (int j = 0; j < lock.size(); j++) {
            if (lock[i][j] == 0) {
                string s = "";
                s += to_string(i);
                s += " "; //" "로 구분
                s += to_string(j);
                blank[s]++; //해쉬에 blank 위치 저장
            }
        }
    }
    
    //lock에 홈이 없을때
    if (blank.empty())
        return true;

    for (int k = 0; k < 4; k++) { //90도 회전
        //key의 돌기부분 vector에 쌍으로 저장
        vector<pair<int, int>> block;
        for (int i = 0; i < key.size(); i++) {
            for (int j = 0; j < key.size(); j++) {
                if (key[i][j] == 1) {
                    block.push_back(make_pair(i, j));
                }
            }
        }

        //lock 홈 부분
        for (auto m : blank) {
            //key 돌기 부분
            for (int n = 0; n < block.size(); n++) {
                stringstream ss(m.first);
                int col, row;
                ss >> col >> row;
                col = block[n].first - col;
                row = block[n].second - row; 
                //key의 돌기부분을 lock의 홈부분으로 이동
                int check = 0; //lock의 홈부분이 모두 채워졌는지 확인
                //모든 key의 돌기부분을 이동
                for (int x = 0; x < block.size(); x++) {
                    int col_b = block[x].first - col;
                    int row_b = block[x].second - row;
                    //key의 돌기가 이동한 위치가 lock의 위치를 벗어났을때
                    if (col_b >= lock.size() || row_b >= lock.size() || col_b < 0 || row_b < 0) {
                        continue;
                    }
                    //lock의 홈부분일 때
                    if (lock[col_b][row_b] == 0)
                        check++;
                    else
                        break;
                }
                //빈칸이 모두 채워졌을 때
                if (check == blank.size())
                    return true;
            }
        }
        rotation(key); //90도 회전
    }

    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) << "\n";
    return 0;
}

 

설명

• lock에서 홈 부분을 찾아 해쉬에 홈의 위치를 띄어쓰기 구분하여 string형태로 저장하였다.
• key에서 돌기부분을 찾아 벡터에 쌍으로 저장하였다.

• 여기서 구한 lock의 홈 부분과 key의 돌기 부분을 하나씩 맞춰보면서 일치하는지 확인하였다. 

일치하지 않는 경우

• lock의 홈부분이 모두 채워지거나 lock의 돌기 부분과 key의 돌기 부분이 맞닿지 않으면 자물쇠를 풀 수 있다. 

일치하는 경우

 

고찰

걸린시간 : 2시간

해결법을 생각하기에는 어렵지 않았지만 오류를 찾는데 시간이 한 시간 정도 걸렸다. 

lock의 크기를 생각하지 않았다. map에 세자리이상 수가 들어갈 생각을 하지 않고 해쉬 맵에 입력하여 배열을 받아오는데 문제가 있었다. (테스트 7,8,11,18,20 실패) 수차례의 디버깅 끝에 찾아낼 수 있었다.

다른 사람의 풀이는 열쇠의 가장 왼쪽 위부분과 가장 오른쪽 아래부분 까지 맞춰볼 수 있도록 lock의 크기 + (key의 크기 -1)*2 크기의 벡터를 만들어주어 모든 경우의 수를 구할 수 있도록 하였다. 모든 방법을 구하기 위해서 다음과 같은 방법도 한 번 풀어봐야 할 거 같다.