[2020카카오공채] 자물쇠와 열쇠

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

프로그래머스

카카오 코딩테스트 문제를 처음부터 풀어보고 있다

이 문제는 3번 문제에 해당하는데, 정답률이 고작 7.4% ㅋㅋㅋㅋㅋ

(물론 뒤쪽 문제로 갈수록 정답률이 점점 더 떨어진다)

카카오가 전면 블라인드 채용을 해서 일단 찔러보기 식으로 지원을 한 지원자도 많을 것 같기 때문에

정답률이 크게 유의미한건 아닌 것 같다.

 

아무튼 1~3번 문제를 풀어본 소감은 구현력이 많이 요구된다는 것!

솔직히 문제 자체는 손도 못댈 정도로 어려운건 아닌데(뒷문제로 가면 어떨지 모르겠지만)

뭔가 문제에서 요구하는 것들이 많다.

 

나만 해도 이 문제를 푸는데 시간을 한참 썼기 때문에..ㅠ_ㅠ

다양한 문제를 많이 풀어보며 구현력을 키워야겠다는 생각을 했다. 5중 for문이 웬말이요..

 

그리고 그간 백준을 풀 때는 쉽고 빠르게 풀기 위해 대충 배열을 최대 사이즈로 잡아 놓고 풀었었는데

카카오는 웬만하면 vector를 쓰는 듯 하다..^^

앞으로 어떤 문제를 어떤 식으로 풀면서 연습해야 할지 약간 가닥이 잡히는 것 같기도 하고..

 

---

 

피곤해서 풀이방법을 다음에 쓰려고 했으나 오늘 안쓰면 영영 안쓸거 같아서 간단히 정리해본다.

 

 

이런 경우도 고려해줘야 함..

이 문제는 주어진 키로 자물쇠를 열 수 있느냐 하는 문제인데,

키와 자물쇠의 크기가 딱 맞아서 정확히 맞물려지는 경우만 있으면 너무 쉽겠으나

키가 자물쇠보다 작거나 같고 키의 일부분을 자물쇠의 일부분에 맞추는 경우도 있기 때문에

다양한 케이스들을 고려해주어야 한다.

그리고 키를 회전시키는 경우도 생각해야 한다.

 

그래서 전체적인 코드는

for (키가 회전하는 경우)

   for (키가 움직이는 경우의 수)

      for (자물쇠를 한칸씩 탐색)

이런 식으로 짜여지게 된다.

 

키가 움직이는 경우의 수를 모두 고려하기 위해, 키의 가장 좌측 상단의 좌표를 기준으로 for문을 돌렸다.

좌측 상단 좌표의 범위는 -key_size+1 ~ lock_size-1이다. (그림을 그려서 생각해보면 편함)

 

자물쇠를 한칸씩 탐색하는 건 인덱스 범위를 0~lock_size-1로 두면 되고..

 

자물쇠를 한 칸씩 탐색하면서 다음의 내용을 검사한다.

1. 현재 좌표의 범위에 키가 있는 경우

    => 자물쇠와 키의 값이 동일하면 자물쇠와 키가 안맞는 것이므로 answer == false 하고 break

2. 현재 좌표의 범위에 키가 없는 경우

    => 자물쇠가 false면, 홈이 있는데 키로 채워지지 않은 것이므로 answer == false 하고 break

 

자물쇠를 한번 탐색한 후 answer가 true면 키와 자물쇠가 일치하는 것이므로 그대로 true를 리턴한다.

 

불일치하면 검사를 계속하는데

키의 모든 위치에 대해 검사가 끝나면 키를 한번 회전시킨 후 다시 검사를 해야 한다.

키의 회전은 별도의 함수로 구현했다.

 

키가 회전하는 경우, 키의 위치가 변경되는 경우를 모두 고려해서 검사가 끝났는데도 solution 함수가 return 되지 않았다면 키로 자물쇠를 열 수 없는 것이므로 false를 리턴한다.

 

무려 5중 for문을 돌려야 하지만 인풋 사이즈가 워낙 작으므로 완전탐색으로도 잘 풀린다.

 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> rotate(vector<vector<int>> key, int key_size) {
	vector<vector<int>> new_key(key_size);

	for (int i = 0; i < key_size; i++) {
		new_key[i].resize(key_size);
	}

	for (int i = 0; i < key_size; i++) {
		for (int j = 0; j < key_size; j++) {
			new_key[i][j] = key[j][key_size - 1 - i];
		}
	}

	return new_key;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	bool answer;
	int key_size = key.size();
	int lock_size = lock.size();

	for (int h = 0; h < 4; h++) {

		// key의 위치를 변경해가면서 for문 돌림(i,j)는 key의 좌측상단
		for (int i = -key_size + 1; i < lock_size; i++) {
			for (int j = -key_size + 1; j < lock_size; j++) {
				answer = true;

				// lock 한칸씩 검사
				for (int k = 0; k < lock_size; k++) {
					for (int l = 0; l < lock_size; l++) {
						// 해당 위치에 key가 존재하는 경우, key와 lock의 값이 같으면 false
						if ((k >= i) && (k < i + key_size) && (l >= j) && (l < j + key_size)) {
							if (key[k - i][l - j] == lock[k][l]) answer = false;
						}

						// 해당 위치에 key가 존재하지 않고 lock이 0인 경우
						else if (lock[k][l] == 0) {
							answer = false;
						}

						if (!answer) break;
					}
					if (!answer) break;
				}

				// lock 검사 후 answer가 true면 true return
				if (answer) return 1;
			}
		}

		// key를 회전
		key = rotate(key, key_size);
	}

	return 0;
}

 

---

 

그리고 카카오에서 올린 문제풀이를 보고 다시 작성해본 코드

자물쇠 가로길이보다 3배 큰 new_lock, new_key 배열을 선언한 뒤

new_lock의 중앙에 기존 lock 배열을 복사하고

new_key 배열에는 key의 위치를 변경해가면서 복사한다.

그리고 new_lock와 new_key를 비교하면 끝!

 

사실 new_lock 배열을 기존 배열보다 3배 크게 잡으면 쓸데없는 연산도 생겨나고 공간복잡도도 커지게 된다.

하지만 배열을 사용할 때 인덱스 참조 에러가 수도없이 일어나고..

그 에러 잡느라 시간을 허비하는 것을 생각해본다면 이 방법으로 푸는게 더 괜찮은 것 같다.

일단 문제를 시간 내로 푸는 것이 가장 중요하니까..T^T

(인풋사이즈가 워낙 작으니 연산속도에 미치는 영향도 미미할 듯 하다)

 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> rotate(vector<vector<int>> key, int key_size) {
	vector<vector<int>> new_key(key_size);

	for (int i = 0; i < key_size; i++) {
		new_key[i].resize(key_size);
	}

	for (int i = 0; i < key_size; i++) {
		for (int j = 0; j < key_size; j++) {
			new_key[i][j] = key[j][key_size - 1 - i];
		}
	}

	return new_key;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
	bool answer;
	int key_size = key.size();
	int lock_size = lock.size();
	int new_size = lock_size * 3;

	// lock 새로운 배열에 할당
	vector<vector<int>> new_lock(new_size);
	for (int i = 0; i < new_size; i++) new_lock[i].resize(new_size);
	for (int i = 0; i < lock_size; i++) {
		for (int j = 0; j < lock_size; j++) {
			new_lock[lock_size + i][lock_size + j] = lock[i][j];
		}
	}

	for (int h = 0; h < 4; h++) {

		// key의 위치 바꿔가며 for문
		for (int i = 0; i <= new_size - key_size; i++) {
			for (int j = 0; j <= new_size - key_size; j++) {

				// key 새로운 배열에 할당
				vector<vector<int>> new_key(new_size);
				for (int k = 0; k < new_size; k++) new_key[k].resize(new_size);
				for (int k = 0; k < key_size; k++) {
					for (int l = 0; l < key_size; l++) {
						new_key[i + k][j + l] = key[k][l];
					}
				}

				// new_key와 new_lock 비교
				answer = true;

				for (int k = lock_size; k < lock_size * 2; k++) {
					for (int l = lock_size; l < lock_size * 2; l++) {
						if (new_key[k][l] == new_lock[k][l]) {
							answer = false;
							break;
						}
						if (!answer) break;
					}
					if (!answer) break;
				}

				// lock 검사 후 answer가 true면 true return
				if (answer) return 1;
			}
		}

		// key를 회전
		key = rotate(key, key_size);
	}

	return 0;
}