[프로그래머스 level3] 자물쇠와 열쇠 (C++)
2020 kakao blind recruitment에서 나왔던 문제로 복잡한 구현문제입니다. (프로그래머스 level3)
문제는 다음과 같습니다.
자물쇠와 열쇠
조건
- key의 크기 M은 lock의 크기 N 이하이다.
- key는 이동과 회전이 가능하다. (90,180,270도 모두 가능)
- key의 돌기부분(1)과 자물쇠의 홈 부분(0)이 일치해야 한다.
- 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있다.
조건이 참 많은 구현문제입니다.
key의 이동과 회전에 대해서 어떻게 짜야할지 감이 안 잡혀 다음의 티스토리를 참고했습니다.
참고
구현과정
- 배열을 N+2(M-1)로 만듭니다.
key가 이동이 가능하기 때문에 lock에 일부만 걸쳐있을 수 있습니다. 따라서 열쇠가 이동가능한 영역은 N+2(M-1) X N+2*(M-1) 가 됩니다.
=> solution() 참고 - 1에서 구한 배열에 lock 부분 할당하기
확장된 배열의 중앙에 lock을 할당합니다.
lock이 아닌부분 -> 2
lock인 부분 -> 0/1
lock의 시작좌표 : (0,0) -> (M-1, M-1)
lock의 종료좌표 : (N,N) -> (배열크기-M, 배열크기-M)
=> make_MAP() 참고 - key, lock을 비교
- key (0), lock (0) -> 틀림
- key (1), lock (1) -> 틀림
- key (1), lock (0) -> 맞음
=> isUnlock() 참고 - key의 이동
key는 N+M-1 만큼 오른쪽, 아래로 움직일 수 있음
=> move_key() 참고 - key의 회전
시계방향으로 90도 회전하면
(y,x) <- (M-1-x,y)
=> rotate_key() 참고
코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> MAP;
int N, M, Size, sum;
void make_MAP(vector<vector<int>> lock)
{
int y = 0, x = 0;
for(int i=M-1; i<Size-M+1; i++, y++)
{
for(int j=M-1; j<Size-M+1; j++, x++)
{
if(lock[y][x]==0) {MAP[i][j] = 0; sum++;}
else MAP[i][j] = 1;
}
x=0;
}
}
int isUnlock(int y, int x, vector<vector<int>> key)
{
int idx_x = 0, idx_y = 0;
int cnt = 0;
for(int i=y; i<y+M; i++, idx_y++)
{
for(int j=x; j<x+M; j++, idx_x++)
{
if(key[idx_y][idx_x]==0 && MAP[i][j]==0) return -1;
if(key[idx_y][idx_x]==1 && MAP[i][j]==1) return -1;
if(key[idx_y][idx_x]==1 && MAP[i][j]==0) cnt++;
}
idx_x=0;
}
return cnt;
}
void rotate_key(vector<vector<int>> &key)
{
vector<vector<int>> tmp = key;
for(int i=0; i<M; i++)
{
for(int j=0; j<M; j++)
{
tmp[i][j] = key[M-1-j][i];
}
}
key = tmp;
}
bool move_key(vector<vector<int>> key)
{
for(int i=0; i<4; i++)
{
//시작칸수
for(int j=0; j<M+N-1; j++)
{
for(int k=0; k<M+N-1; k++)
{
if(isUnlock(j,k,key)==sum)
{
return true;
}
}
}
rotate_key(key);
}
return false;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
bool answer = true;
M = key.size();
N = lock.size();
Size = N+(M-1)*2;
MAP.resize(Size, vector<int>(Size,2));
make_MAP(lock);
if(!move_key(key)) answer = false;
return answer;
}
c++ 문법
- 2차원 배열 -> vector <vector<int>> v
(크기를 모를때 int arr[][] 보다 좋은 듯) - vector 크기 지정 및 값 할당
- 선언시 할당
vector<int> vec(5,1) - 재할당 or 선언 이후 할당
vec.resize(10,2)
[resize 주의할점]
resize하며 더 커지는 경우에만 값이 들어간다.
더 작아지는 경우에는 크기만 작아지고 값이 할당되지는 않는다.
이 코드에서는
MAP.resize(Size, vector<int>(Size,2));
이렇게 사용하였다.
2차원 vector를 size만큼 지정하고 vector (size,2)의 값을 할당한다는 의미
즉 모든 값을 2로 할당
Author And Source
이 문제에 관하여([프로그래머스 level3] 자물쇠와 열쇠 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mar_f/프로그래머스-자물쇠와열쇠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)