[Lv.3] 자물쇠와 열쇠

삽질코드(82/100)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        int n=lock.length;
        List<Point> lockPoints=new ArrayList<>();
        Point initPoint,endPoint;
        initPoint=new Point(n,n);
        endPoint=new Point(-1,-1);
        for (int i = 0; i < lock.length; i++) {
            for (int j = 0; j < lock[i].length; j++) {
                if(lock[i][j] == 0){
                    lockPoints.add(new Point(i,j));
                    if(i< initPoint.x)
                        initPoint=new Point(i, initPoint.y);
                    if(j< initPoint.y)
                        initPoint=new Point(initPoint.x, j);
                    if(i> endPoint.x)
                        endPoint=new Point(i, endPoint.y);
                    if(j> endPoint.y)
                        endPoint=new Point(endPoint.x, j);

                }
            }
        }
        //왼위 오아래 기준으로 직사각형을 만들어서 자르자
        //그 직사각형이 pXq라면
        //Key를 어떻게 어떻게 해서 pXq 형태로 만들고 이게 맞는 지 확인해야 할 듯..
        int sqrX= endPoint.x- initPoint.x;
        int sqrY= endPoint.y- initPoint.y;
        //여기서 1,1 ` 1,2 이렇게 1x2 직사각형인 경우 sqrx=0, sqry=1
        int lockSize=lockPoints.size();
        if(lockSize==0) {
            return false;
        }
        //lock의 init을 0 으로 잡고 LockPoint를 다시 설정한다.
        Point finalInitPoint = initPoint;
        for (int i = 0; i < lockPoints.size(); i++) {
            Point point = lockPoints.get(i);
            point.x= point.x- finalInitPoint.x;
            point.y= point.y- finalInitPoint.y;
        }


        for (int i = 0; i < key.length; i++) {
            for (int j = 0; j < key.length; j++) {
                if(j+sqrY< key.length&&i+sqrX<key.length){
                    List<Point> targetKeyList1=new ArrayList<>();
                    List<Point> targetKeyList2=new ArrayList<>();
                    List<Point> targetKeyList3=new ArrayList<>();
                    List<Point> targetKeyList4=new ArrayList<>();
                    for (int k = i; k <= i+sqrX; k++) {
                        for (int l = j; l <= j+sqrY; l++) {
                            if(key[k][l]==1) {
                                //왼위 부터 검사를 시작하고 그걸 0으로 봐야한다
                                targetKeyList1.add(new Point(k-i,l-j));
                                targetKeyList2.add(new Point(l-j,sqrX-(k-i)));
                                targetKeyList3.add(new Point(sqrX-(k-i),sqrY-(l-j)));
                                targetKeyList4.add(new Point(sqrY-(l-j),k-i));
                            }
                            if(lockSize<targetKeyList1.size()){
                                break;
                            }
                        }
                    }
                    if(targetKeyList1.size()!=lockSize)
                        continue;
                    if(lockPoints.containsAll(targetKeyList1)||lockPoints.containsAll(targetKeyList2)
                            ||lockPoints.containsAll(targetKeyList3)||lockPoints.containsAll(targetKeyList4)){
                        return true;
                    }
                }
                if(i+sqrY< key.length&&j+sqrX<key.length){
                    List<Point> targetKeyList1=new ArrayList<>();
                    List<Point> targetKeyList2=new ArrayList<>();
                    List<Point> targetKeyList3=new ArrayList<>();
                    List<Point> targetKeyList4=new ArrayList<>();
                    for (int k = i; k <= i+sqrY; k++) {
                        for (int l = j; l <= j+sqrX; l++) {
                            if(key[k][l]==1) {
                                //왼위 부터 검사를 시작하고 그걸 0으로 봐야한다
                                targetKeyList1.add(new Point(k-i,l-j));
                                targetKeyList2.add(new Point(l-j,sqrY-(k-i)));
                                targetKeyList3.add(new Point(sqrY-(k-i),sqrX-(l-j)));
                                targetKeyList4.add(new Point(sqrX-(l-j),k-i));
                            }
                            if(lockSize<targetKeyList1.size()){
                                break;
                            }
                        }
                    }
                    if(targetKeyList1.size()!=lockSize)
                        continue;
                    if(lockPoints.containsAll(targetKeyList1)||lockPoints.containsAll(targetKeyList2)
                            ||lockPoints.containsAll(targetKeyList3)||lockPoints.containsAll(targetKeyList4)){
                        return true;
                    }
                }

            }
        }

        return false;
    }
    class Point{
        int x;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Point point = (Point) o;

            if (x != point.x) return false;
            return y == point.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

정답코드

import java.util.*;

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;

        int m = key.length;
        int n = lock.length;

        int len = n+m*2-2;
        int[][] map = new int[len][len];    // 확장시킨 배열

        /* 확장시킨 배열에 Lock 표시 */
        for(int i=m-1; i<m+n-1 ; i++){
            for(int j=m-1; j<m+n-1; j++){
                map[i][j] = lock[i-(m-1)][j-(m-1)];
            }
        }

        /* 4번 조사 */
        for(int i=0; i<4; i++){
            if(check(map, key, n)){
                return true;
            }
            rotate(key); // 시계방향 90도 회전
        }


        return false;
    }

    /* 키가 자물쇠에 맞는지 체크 */
    public static boolean check(int[][] map, int[][] key, int lockLen){
        int keyLen = key.length;
        int mapLen = map.length;
        for(int i=0; i<mapLen-keyLen+1; i++){
            for(int j=0; j<mapLen-keyLen+1; j++){

                /* map에 key를 더함 */
                for(int k=0; k<keyLen; k++){
                    for(int l=0; l<keyLen; l++){
                        map[i+k][j+l] += key[k][l];
                    }
                }

                /* 자물쇠 부분이 전부 1이 됐는지 확인 */
                boolean flag = true;
                for(int k=keyLen-1; k<keyLen+lockLen-1; k++){
                    for(int l=keyLen-1; l<keyLen+lockLen-1; l++){
                        if(map[k][l] != 1){ // 1이 아니면 홈이 안 맞는 것임
                            flag = false;
                            break;
                        }
                    }
                    if(!flag) break;
                }

                if(flag) return true;   // 전부 1이였다면 true

                /* map을 원상 복귀 시킴 -> map에서 key를 뺌 */
                for(int k=0; k<keyLen; k++){
                    for(int l=0; l<keyLen; l++){
                        map[i+k][j+l] -= key[k][l];
                    }
                }

            }
        }

        return false;
    }

    /* key 시계 방향 90도 회전 */
    public static void rotate(int[][] key){
        int len = key.length;
        int[][] temp = new int[len][len];

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

        for(int i=0; i<len; i++){
            for(int j=0; j<len; j++){
                key[i][j] = temp[i][j];
            }
        }

    }
}

 

 

---

엄청난 삽질을 한 문제였다.

난, 열쇠로 자물쇠를 푸는 게 열쇠를 회전하고 초콜릿 떼어내듯이 아래로 한 칸 밀면 아래 한칸을 떼어내고 옆으로 또 밀면 옆에 한 줄을 또 떼내는 방식인줄 알았다....

처음 코드를 냈을 땐, 15번 이후의 케이스들이 오류를 내더니 수정하여 제출하니 앞번호의 케이스들이 오류를 냈다.

로직에 문제는 없는 것 같아 문제를 다시 보니 민다는 뜻이 열쇠 판을 자물쇠 판 기준 빈공간으로 밀면서 끼워 넣는 것이였다.(마치 손바닥 맞대듯이..)

이러한 문제가 sliding window 라는 유형인데, 처음 풀어봐서 그런지 접근 방법을 잘 못 잡은 것 같다.

다음에 sliding window 문제를 만나면 꼭 눈치채고 바로바로 풀어야 겠다..