2020 카카오 공채: 자물쇠와 열쇠

[문제 링크]

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

---

N과 M의 최대 길이가 20으로 완전탐색을 돌리면 무난히 풀 수 있는 문제였다.

 

하지만 풀이법을 떠올리기가 정말 어려웠던거 같다.

 

처음엔 key 배열을 회전시키는 함수와 상하좌우로 한칸씩 밀어내는 함수를 구현해서 풀려고 했는데 조금만 생각해봐도 무수한 반례가 존재하는 풀이였다.

 

key를 모든 경우에 대조하기 위한 다른사람의 풀이법을 참고하기 위해 찾아보다 좋은 풀이법을 발견하고 바로 구현할 수 있었다.

 

https://regularmember.tistory.com/186

프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++

---

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> rotate(const vector<vector<int>>& key)
{
	int len = key[0].size();
	vector<vector<int>> ret(len);

	for(int i=0; i<len; i++)
		for (int j = 0; j < len; j++)
			ret[i].push_back(key[len-1-j][i]);

	return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	int M = key[0].size(), N = lock[0].size();
	int T = N + (M - 1) * 2;
	vector<vector<int>> total(T);
	
	int concave = 0;

	for(int i = 0; i < T; i++)
		for (int j = 0; j < T; j++)
		{
			if ((i >= M - 1 && j >= M - 1) && (i <= T - M && j <= T - M))
			{
				total[i].push_back(lock[i-(M-1)][j-(M-1)]);
				if (lock[i-(M-1)][j-(M-1)] == 0)
					concave++;
			}
			else
				total[i].push_back(2);

		}

	for (int i = 0; i < 4; i++)
	{
		for (int startY = 0; startY <= T - M; startY++)
		{
			for (int startX = 0; startX <= T - M; startX++)
			{
				bool check = true;
				int remain = concave;

				for (int keyY = 0; keyY < M; keyY++)
				{
					for (int keyX = 0; keyX < M; keyX++)
					{
						int keyVal = key[keyY][keyX];
						int totalVal = total[startY + keyY][startX + keyX];

						if (keyVal == totalVal)
						{
							check = false;
							break;
						}
						if (keyVal == 1 && totalVal == 0)
							remain--;
					}
					if (!check) break;
				}
				if (check && remain == 0)
					return true;
			}
		}

		key = rotate(key);
	}

	return false;
}

알고리즘 200일 프로젝트 - 138 day