Programmers [2020 KAKAO BLIND RECRUITMENT]: 자물쇠와 열쇠 풀이 및 코드

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

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

Key배열을 회전 및 이동시켜서 Lock배열과 비교하는 문제 !!

문제를 풀기 위해서는 배열 회전 코드를 외워놓으면 풀기 용이하다

 

전체적인 수도 코드 알고리즘은 다음과 같다

1. Lock배열의 3배 크기인 배열을 새로 생성한다

2. 1번에서 만든 배열 속의 Lock배열과 Key배열이 겹치도록 1번과 같은 크기의 배열을 생성하고 key배열을 이동시킨다

3. Lock배열과 Key배열을 XOR 연산해서 Lock배열 위의 연산값이 1이 되는지 판단해서 된다면 true를 반환

4. 3번이 실패했다면 Key배열을 다음 좌표로 이동시킨다

5. Key배열을 더 이상 이동시킬 수 없다면 90도 회전한 뒤 2번으로 돌아간다

 

문제 풀이 노트

코드는 아래와 같다 😊

#include <string>
#include <vector>
#include <cstring>

using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	bool answer = true;
	int temp[25][25] = { 0 }, locks[65][65] = { 0 }, copy[65][65];
	const int start = lock.size();

	for (int i = 0; i < lock.size(); i++)
		for (int j = 0; j < lock.size(); j++)
			locks[lock.size() + i][lock.size() + j] = lock[i][j];

	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < key.size(); i++)
			for (int j = 0; j < key.size(); j++)
				temp[i][j] = key[key.size() - 1-j][i];
		for (int i = 0; i < key.size(); i++)
			for (int j = 0; j < key.size(); j++)
				key[i][j] = temp[i][j];

		for (int i = 0; i < lock.size() * 2; i++)
			for (int j = 0; j < lock.size() * 2; j++) {   //모든 좌표에 대해 copy&paste
				memset(copy, 0, sizeof(copy));

				for (int a = 0; a < key.size(); a++)
					for (int b = 0; b < key.size(); b++)
						copy[i + a][j + b] = key[a][b];   //copy배열로 복사

				bool check = true;
				for (int a = start; a < start*2; a++)
					for (int b = start; b < start * 2; b++)
						if (!(locks[a][b] ^ copy[a][b])) {
							check = false;
							break;
						}
				if (check)return true;
			}
	}
	return false;
}

시간복잡도는 Lock배열크기 - N, Key배열 크기 - M (M<=N<=20) 이므로 O(N^2*M*2)이고,

완전탐색해도 시간제한 내에 해결 가능하다.