[2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠 (JAVA)

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

 

먼저 key의 돌기 부분(1) 좌표를 저장하고 lock의 홈 부분(0)의 좌표를 저장해뒀다.

예제의 key 돌기 부분 좌표 : (1,0) (2,1) (2,2)

예제의 lock 홈 부분 좌표 : (1,2) (2,1)

 

이제 다음과 같이 진행한다.

1. key의 돌기 좌표를 반복문을 이용해 하나를 선택해서 lock의 홈 좌표 위치중 하나에 맞춘다.

    ex. (1,0)을 (1,2)에 맞추기 위해서 x좌표는 +0, y좌표는 +2 해주면 된다.

    ps. (1,0) -> (1,2) (+0,+2)  / (1,0) -> (2,1) (+1,+1)  / (2,1) -> (1,2) (-1,+1) / (2,1) -> (2,1) (+0, +0) / (2,2) -> (1,2)  (-1,+0) / (2,2) -> (2,1) (+0, -1)

2. 나머지 key의 돌기 좌표들을 위에서 구한 만큼 이동시켜 본다.

    2-1. 만약 lock 돌기 좌표와 만나면 해당 이동 거리는 답이 될 수 없다. 전부 체크해 보지 않았다면 다시 1번으로 돌아간다.

3. lock이 풀리지 않았다면 오른쪽으로 90도 회전시켜서 반복한다.

 

※ lock이 모두 1로 되어있으면 true로 반환하는 예외처리를 해줘야 한다.

import java.util.ArrayList;
import java.util.List;
 
public class 자물쇠와열쇠 {
    // M은 key, N은 자물쇠
    static int M, N;
    
    // 좌표 클래스
    static class Pos {
        int x, y;
 
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    // 0은 홈, 1은 돌기
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        M = key.length;
        N = lock.length;
 
        List<Pos> keyList = new ArrayList<Pos>();
        List<Pos> lockList = new ArrayList<Pos>();
        
        // key의 돌기 부분 좌표를 저장
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                if (key[i][j] == 1)
                    keyList.add(new Pos(i, j));
            }
        }
        
        // lock의 홈 부분 좌표를 저장
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (lock[i][j] == 0)
                    lockList.add(new Pos(i, j));
            }
        }
        
        // lock이 모두 돌기이면 무조건 true 리턴
        if (lockList.size() == 0)
            return true;
 
        // 0도, 90도, 180도, 270도 돌리고 확인
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < keyList.size(); j++) {
 
                Pos keyPos = keyList.get(j);
 
                for (int k = 0; k < lockList.size(); k++) {
                    boolean flag = true;
                    Pos lockPos = lockList.get(k);
                    int dx = lockPos.x - keyPos.x;
                    int dy = lockPos.y - keyPos.y;
                    int cnt = 1;
 
                    for (int w = 0; w < keyList.size(); w++) {
                        if (j == w)
                            continue;
 
                        Pos keyPos2 = keyList.get(w);
                        int nx = keyPos2.x + dx;
                        int ny = keyPos2.y + dy;
                        
                        // key가 lock 영역 밖이면 상관없음.
                        if (!isLockRange(nx, ny))
                            continue;
 
                        // key의 돌기와 lock의 홈이 만나면 카운트 증가
                        if (lock[nx][ny] == 0)
                            cnt++;
                        
                        // key의 돌기와 lock의 돌기가 만나면 안되므로 종료
                        if (lock[nx][ny] == 1) {
                            flag = false;
                            break;
                        }
                    }
                    if (!flag)
                        break;
                    
                    // lock의 홈이 모두 채워졌으면 true 리턴
                    if (cnt == lockList.size())
                        return true;
                }
            }
 
            // key 회전
            if (i != 3)
                keyList = Rotation(keyList);
        }
        return answer;
    }
    
    // key를 움직였을 때 key의 돌기 부분이
    // lock의 영역 내에 있는지를 확인하기 위한 함수
    static boolean isLockRange(int x, int y) {
        return (x >= 0 && y >= 0 && x < N && y < N);
    }
 
    // 오른쪽으로 90도 회전
    static List<Pos> Rotation(List<Pos> keyList) {
        List<Pos> tmp = new ArrayList<Pos>();
 
        for (Pos p : keyList) {
            tmp.add(new Pos(p.y, M - 1 - p.x));
        }
 
        return tmp;
    }
}