[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠 -Java

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

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

import java.util.ArrayList;
import java.util.List;
class Solution {
		class Point{
			int x,y;
			public Point(int x, int y) {
				this.x = x;
				this.y = y;
			}
		}
	    public boolean solution(int[][] key, int[][] lock) {
	        boolean answer = false;
	        int M=key.length; //열쇠
	        int N=lock.length; //자물쇠
	        int size=N+(2*M)-2;
	        int map[][]=new int[size][size];
	        
	        int fillCnt=0; //맞춰야 되는 홈 개수
	        for(int i=0; i<N; i++) {
	        	for(int j=0; j<N; j++) {
	        		if(lock[i][j]==0) fillCnt++; 
	        	}
	        }
	        
	        int idx=0; //큰맵 만들어서 자물쇠 넣어주기 
	        for(int i=M-1 ; i<M-1+N; i++) {
	        	System.arraycopy(lock[idx++], 0, map[i], M-1, N);
	        }
	        
	        
	        List<Point> list = new ArrayList<>();
	        
	        //열쇠 돌기부분 list에 넣기 
	        for(int i=0; i<key.length; i++) { 
	        	for(int j=0; j<key[i].length; j++) {
	        		if(key[i][j]==1) list.add(new Point(i,j));
	        	}
	        }
	        
	        //각각 90도로 돌려서 시작 
	        for(int i=0; i<4; i++) {
	        	if(solve(list,lock, N,M,fillCnt,map)) {
	        		answer=true;
	        		break;
	        	}
	        	
	        	for(int j=0; j<list.size(); j++) {
	        		Point point=list.get(j);
	        		int x=point.y;
	        		int y=(M-1)-point.x;
	        		point.x=x;
	        		point.y=y;
	        	}
	        }
	        return answer;
	    }

		private boolean solve(List<Point> list, int[][] lock, int N, int M, int fillCnt, int[][] map) {
		
			for(int i=0; i<M-1+N; i++) {
				loop :for(int j=0; j<M-1+N; j++) {
					int cnt=0; //몇개나 맞는지 
					//List<Point> copy=new ArrayList<>(list);
					List<Point> copy=new ArrayList<>();
					for(Point point : list) {
						int x=point.x;
						int y=point.y;
						copy.add(new Point(x,y));
					}
					for(int k=0; k<list.size(); k++) {
						//열쇠 옮겨주기 
						Point point=copy.get(k);
						point.x+=i;
						point.y+=j;
					}
					
					//열쇠 다옮겻으면 자물쇠의 홈과 키의 돌기가 맞는지 확인
					for(int k=0; k<copy.size(); k++) {
						//열쇠 옮겨주기 
						Point point=copy.get(k);
						
						//자물쇠 범위에 맞다면 
						if(point.x>=M-1 && point.x<M-1+N &&point.y>=M-1 && point.y<M-1+N) {
							if(map[point.x][point.y]==1) continue loop; //돌기와 돌기가 마주치면 넘어감 
							cnt++; //자물쇠 맞다면 cnt늘려줌
						}
						
					}
					if(cnt==fillCnt) return true;
				}
			}
			return false; 
		}
	}

소요시간 : 1시간 10분

 

예전에 풀려고 했다가 실패했던 문제인데 이제 풀리는 걸 보면 실력이 조금 늘었나 보다..!

큰 로직으로는 map이라는 배열을 만드는데 이 배열은 N+(2*M)-2의 크기로 만들었다. 이렇게 만들면 열쇠가 자물쇠 밖으로 나가는 것을 따로 처리해 주지 않아도 된다. 그리고 map 안에 자물쇠를 넣어준다.

 

그리고 lock 배열의 빈 공간의 개수를 체크하고 key 배열에서 1자리를 list에 저장해 준다.
key 배열을 저장한 list를 90도로 돌리면서 solve 함수로 들어간다.

 

solve에서는 map 안에 for 문을 돌면서 (0,0부터 M-1+N, M-1+N) 확인한다. 상하좌우로 움직이는 것은 저 for 문으로 해결된다. 이때 copy라는 리스트를 만들어서 list를 복사해서 사용해 준다. 복사하지 않으면 원래 list의 값이 계속 바뀌기 때문이다

( 복사할 때 List<Point> copy=new ArrayList<>(list); 이렇게 했다가 틀려서 바로 바꾸었다..... 얕은 복사인지 몰랐다..)

그리고 copy에서 값을 하나씩 꺼내서 map 안에 있는 자물쇠의 범위 안에 들어간다면 자물쇠가 0인지 1인지 체크해 주었다!

 

그렇게 어려운 문제는 아니었지만 90도로 돌릴 때 인덱스 규칙을 찾는 것과 map 배열 안의 인덱스를 만들거나 조작하는 것이 조금 힘들었던 문제였습니다!