[프로그래머스] 자물쇠와 열쇠

 

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

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

 

프로그래머스에 있는 카카오 블라인드 테스트 문제이고, 레벨3으로 나온다.

처음에는 lock 범위 내에서 key 가 모두 들어갈 수 있는지만 확인하였으나, 절반은 맞고 절반은 틀린 에러가 발생하였다.

이 말은 즉슨 알고리즘에 문제가 있다는 것이고, 다시 확인한 결과 영역을 벗어나더라도 lock 배열에 있는 값이 모두 1을 만족해야 통과 가능하다는 것을 확인하고 코드 수정 중에 있다.

 

실패한 코드는 아래와 같다.

package com.ndj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Time;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        int[][] key = {{0,0,0},{1,0,0},{0,1,1}};
        int[][] lock = {{1,1,1},{1,1,0},{1,0,1}};
        System.out.println(solution(key,lock));
    }

    public static boolean solution(int[][] key, int[][] lock) {
        for (int d = 0; d < 4; d++) {
            if (rotate(d,key,lock)) return true;
        }
        return false;
    }

    public static boolean rotate(int d, int[][] key, int[][] lock) {
        int new_key[][] = new int[key.length][key.length];
        int zero_count = 0;
        for (int i = 0; i < key.length; i++) {
            for (int j = 0; j < key.length; j++) {
                if (d == 0) {
                    new_key[i][j] = key[i][j];
                }
                if (d == 1) {
                    new_key[j][key.length-1-i] = key[i][j];
                }
                if (d == 2) {
                    new_key[key.length-1-i][key.length-1-j] = key[i][j];
                }
                if (d == 3) {
                    new_key[key.length-1-j][i] = key[i][j];
                }
            }
        }
        for (int i = 0; i < lock.length; i++) {
            for (int j = 0; j < lock.length; j++) {
                if (lock[i][j] == 0) zero_count++;
            }
        }

        for (int i = 0; i < lock.length; i++) {
            for (int j = 0; j < lock.length; j++) {
                if (isCheck(new_key,lock,i,j,zero_count))
                    return true;
            }
        }
        return false;
    }


    public static boolean isCheck(int[][] key, int[][] lock, int start_y, int start_x, int zero_count) {
        int count = 0;
        for (int i = 0; i < key.length; i++) {
            for (int j = 0; j < key.length; j++) {
                int ny = start_y + i >= lock.length ? 0 : start_y + i;
                int nx = start_x + j >= lock.length ? 0 : start_x + j;
                if (key[i][j] == 1 && lock[ny][nx] == 0) {
                    count++;
                }
            }
        }
        return zero_count == count ? true : false;
    }
}

이 코드를 실행시켰을 때, 예제는 동작하였으나 아래 링크에 있는 것과 같은 케이스가 동작하지 않는 문제가 있었다.

* https://moonsbeen.tistory.com/90

[프로그래머스]자물쇠와 열쇠 - JAVA

 

배열 값 계산에 착오가 있었다는 것을 알게 되었고, key 길이 * 2 + lock 길이 배열을 새로 만들어서 처리하는 방식으로 새로 구현하였다.

수정한 코드는 아래와 같습니다.

• match : 새로 생성한 배열에 key 배열을 조합하는 함수
• check : lock 배열 값이 모두 1인 경우  true, 그렇지 않으면 false

수정된 코드

class Solution {
    public static boolean solution(int[][] key, int[][] lock) {
        int point = key.length - 1;
        for(int y = 0; y < point + lock.length; y++) { 
            for(int x = 0; x < point + lock.length; x++) {
                // 0 : 그대로, 1 : 90도 시계방향, 2 : 180도 시계방향, 3 : 90도 반시계방향
                for(int r = 0; r < 4; r++) {
                    int[][] newLock = new int[lock.length + key.length * 2][lock.length + key.length * 2];
                    for(int i = 0; i < lock.length; i++) {
                        for(int j = 0; j < lock.length; j++) {
                            newLock[i + point][j + point] = lock[i][j]; //확장 배열 초기화
                        }
                    }
                    match(newLock, key, r, x, y);  //newLock 배열과 key 맞추기
                    if(check(newLock, point, lock.length)) return true; //자물쇠 영역이 모두 유효한 값인지 확인
                }
            }
        }
        return false;
    }

    public static void match(int[][] newLock, int[][] key, int d, int y, int x) {
        for (int i = 0; i < key.length; i++) {
            for (int j = 0; j < key.length; j++) {
                if (d == 0) {
                    newLock[y+i][x+j] += key[i][j];
                }
                if (d == 1) {
                    newLock[y+i][x+j] += key[j][key.length-1-i];
                }
                if (d == 2) {
                    newLock[y+i][x+j] += key[key.length-1-i][key.length-1-j];
                }
                if (d == 3) {
                    newLock[y+i][x+j] += key[key.length-1-j][i];
                }
            }
        }
    }

    public static boolean check(int[][] newLock, int point, int len) {
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(newLock[point + i][point + j] != 1) return false;
            }
        }
        return true;
    }
}

 

처음에 봤을 때는 어려운 문제라고 생각들지는 않았는데, 자세하게 요구사항을 보니 어려운 문제였던 거 같다.