프로그래머스 _ 자물쇠와 열쇠

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

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

---

풀이방법

확장된 배열

1. 열쇠 4방향으로 회전한 값 저장

2. 확장된 배열을 만들어서 자물쇠와 키가 맞는지 확인!

3. n, m의 최대값이 작아서 충분히 하나하나 비교해서 풀어도 가능!

(회전방향(4) x (m-1+n)^2 x n^2)정도의 연산이라 충분!!

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> originBoard;
vector<vector<vector<int>>> allRotationKey;
int m, n;


void printVec(const vector<vector<int>>& vec)
{
	for (auto ele : vec)
	{
		for (auto ele2 : ele)
			cout << ele2 << ' ';
		cout << '\n';
	}
}

vector<vector<int>> RotationArray(const vector<vector<int>>& a)
{
	//vector space init
	vector<vector<int>> result;
	result.resize(a.size());
	for (int i = 0; i < result.size(); i++)
		result[i].resize(a[i].size());

	//rotation
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < a[i].size(); j++)
			result[i][j] = a[a.size()-1 - j][i];

	return result;
}

bool IsCorrect(const vector<vector<int>>& board)
{
	for (int i = m - 1; i < (m - 1 + n); i++)
		for (int j = m - 1; j < (m - 1 + n); j++)
			if (board[i][j] != 1)
				return false;
	return true;
}

void MakeBoard(const vector<vector<int>>& lock)
{
	originBoard.resize(2*(m - 1) + n);
	for (int i = 0; i < originBoard.size(); i++)
		originBoard[i].resize(2 * (m - 1) + n);

	for (int i = m - 1; i < m - 1 + n; i++)
		for (int j = m - 1; j < m - 1 + n; j++)
			originBoard[i][j] = lock[i - (m - 1)][j - (m - 1)];
}

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

	//1. 4방향의 열쇠 만들기
	allRotationKey.resize(4);
	allRotationKey[0] = key;
	for (int i = 1; i < 4; i++)
		allRotationKey[i] = RotationArray(allRotationKey[i - 1]);

	//2. originBoard 만들기
	MakeBoard(lock);

	// lock이 처음부터 1인경우
	if (IsCorrect(originBoard) == true)
		return true;

	//3. ㄱㄱ
	int cnt = 0;
	for (int keyNum = 0; keyNum < 4; keyNum++)
	{
		for (int i = 0; i < m - 1 + n; i++)
		{
			for (int j = 0; j < m - 1 + n; j++)
			{
				//비교
				vector<vector<int>> temp = originBoard;
				for (int k = i; k < i + m; k++)
					for (int p = j; p < j + m; p++)
						temp[k][p] = (originBoard[k][p] != allRotationKey[keyNum][k - i][p - j]);

				if (IsCorrect(temp) == true)
					return true;
			}
		}
	}

	return answer;
}

---

로직은 분명히 쉬웠는데 작은 부분에 실수가 잦아서 오래걸렸다.ㅠ