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

 

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

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

 

자물쇠와 열쇠

---

 

난이도 :  Level 3

 

 순수 구현력을 시험하는 문제라고 생각합니다. 문제를 확실하게 이해하는 것이 중요해보입니다. 저 같은 경우는 lock과 key가 돌기가 만나는 경우 (둘 다 1인경우)를 처리를 안해줘서 꽤나 시간을 썼습니다. 

 

 저는 다음과 같은 로직으로 문제를 풀고자 했습니다. 

1. key 배열로 Lock 배열을 전탐색해야한다. 

2. key 배열과 Lock 배열을 포함할 수 있는 새로운 배열을 만들어야한다. 

3. 새로운 배열은 Lock 배열의 (0,0)과 (Lock.length - 1, Lock.length - 1)의 점을 하나라도 포함할 수 있는 크기여야 한다.

4. key 배열의 길이 -1한 값을 offset으로 설정한다. 

5. Lock 배열의 길이 + (offset * 2) 로 새로운 배열을 만든다. 

6. 새로 만들 배열 정중앙에 Lock 배열을 그대로 복사한다. 

7. key 배열을 총 4번, 시계 방향 90도로 회전 시킬 수 있다. 

8. key 배열로 새로 만들 배열 (0,0) 부터 탐색한다.

9. 정중앙을 검사하며 모든 값이 1이면 true 아니면 false를 반환한다.

10.false면 위의 과정 반복.

 

 

 

- boolean solution(int[][] key, int[][] lock)

 key 배열의 길이 - 1한 값을 offset 변수로 설정해뒀습니다. offset 변수는 lock 배열에서 최소 하나의 원소를 겹칠 수 있도록하는 변수입니다. 즉, 새로 만든 배열의 길이를 기존 lock 배열의 길이에서 (2*offset)한 값을 더하여 설정합니다. 

 

 lock 배열의 좌측 바깥부터 우측 바깥까지 최소 하나의 격자가 겹칠 수 있도록 2번째 반복문까지 범위를 설정해줍니다. 3번째 반복문은 시계 방향으로 90도 회전할 수 있는 반복문입니다. 3번재 반복문안에서 새로운 배열을 생성해줍니다. 새로운 배열 정중앙에 기존 lock배열의 원소를 복사합니다. rotate() 함수를 호출하여 key를 시계 방향으로 90도 회전하고, 정중앙에서 key 배열과 교차된 lock 배열의 원소를 탐색하는 check() 함수를 호출합니다. 모든 값이 1이면 true를 반환합니다.  

 

 

 

- int[][] rotate(int [][]key)

  key 배열을 시계 방향으로 90도 회전하는 함수입니다.  

 

 

 

- boolean check(int [][]map, int[][] key,int[][] lock, int s, int e,int offset)

  회전된 key 배열을 새로 만든 map과 교차합니다. 두 값다 1이면 lock의 돌기와 key의 돌기가 만나는 것이므로 0을 map에 넣어줍니다. 즉, xor 연산이 필요합니다. 또한, map의 값이 0인 경우에만 key의 값을 map에 넣어줍니다. 

 

 그 다음 map의 정중앙에 위치한 lock 배열을 검사하여 0값이 존재하면 false를 리턴합니다.  

 

 

  코드

class PM_60059 {
	// PM / 60059번 / 자물쇠와 열쇠 / 구현, 문자열 / Level2 / 2020 KAKAO BLIND
	
    public boolean solution(int[][] key, int[][] lock) {
    	int offset = key.length-1;
    	
    	for(int i=0; i<lock.length+offset; i++) {
    		for(int j=0; j<lock.length+offset; j++) {
    			for(int rot=0; rot<4; rot++) {
    				int map[][] = new int[lock.length+(2*offset)][lock.length+(2*offset)];
    				
    				for(int r=0; r<lock.length; r++) {
    					for(int c=0; c<lock.length; c++) {
    						map[r+offset][c+offset] = lock[r][c];
    					}
    				}
    				
    				key = rotate(key);
    				if(check(map, key,lock,i,j,offset)) {
    					return true;
    				};
    			}
    		}
    	}
        return false;
    }
    
    // 시계 방향 90도 회전
    public int[][] rotate(int [][]key) {
    	int result[][] = new int[key.length][key.length];
    	
    	for(int i=0; i<key.length; i++) {
    		for(int j=0; j<key.length; j++) {
    			result [j][key.length-i-1] = key[i][j];
    		}
    	}
    	return result;
    }
    
    public boolean check(int [][]map, int[][] key,int[][] lock, int s, int e,int offset) {

    	for(int i=0; i<key.length; i++) {
    		for(int j=0; j<key.length; j++) {
    			// 2차 실수 - key의 돌기와 lock의 돌기가 만나면 xor 비트 연산을 해야한다. 
    			if(map[i+s][j+e] == 1 && key[i][j] == 1) {
    				map[i+s][j+e] = 0;
    			}
    			//lock 의 돌기가 0인 경우 
    			else if(map[i+s][j+e] == 0) {
    				map[i+s][j+e] = key[i][j];    				
    			}
    		}
    	}
    	
    	// 1차 실수 - 새로운 배열의 lock을 검사하여야 한다. 
		for(int r=0; r<lock.length; r++) {
			for(int c=0; c<lock.length; c++) {
				if(map[r+offset][c+offset] == 0) {
					return false;
				}
			}
		}
    	return true;
    }
}

 

 

 

 

피드백 환영합니다.