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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

이문제는 레벨3 문제치고는 쉬운 구현문제입니다.

 

기억해야할점

 

첫번쨰. 여기서 Lock의 길이인 N을 넣었어야햇는데 M을 넣어서 오랫동안 해맸습니다.

그냥 직관적으로 N, M 하지말고 lock.length로 하는것이 좋아보입니다.

//Board의 lock부분쪽을 다시 lock으로 초기화시킵니다.
for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
        Board[(M-1)+i][(M-1)+j] = Lock[i][j];
    }
}

 

두번쨰, M은 항상 N 이하입니다.

이 조건을 처음에 못봐서 M이 큰 경우, N이 큰경우를 나눠서 구현하는중에 봤습니다.

 

 

세번쨰, 자물쇠와 열쇠를 새로 구현해줄떄 N + (M-1)*2 를 생각해낼떄 살짝 어려움이 있을 수 있습니다.

자물쇠를 한번 더하고 (열쇠 크기-1)의 크기를 2번 더한다고 쉽게 생각합니다.

그림으로 확인해보면 쉬어집니다.

Board = new int[ N + (M-1)*2][ N + (M-1)*2];

 

 

코드입니다.

class Solution {
    
    int N;
    int M;
    int[][] Board;
    int[][] temp;
    int[][] Lock;
    int[][] Key;
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        N = lock.length;
        M = key.length;
        Lock = lock;
        Key = key;
        //자물쇠가 더 큰경우(M은 항상 N이하이다..)
        Board = new int[ N + (M-1)*2][ N + (M-1)*2];
        temp = new int[ N + (M-1)*2][ N + (M-1)*2];
        //Board의 lock부분쪽을 다시 lock으로 초기화시킵니다.
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                Board[(M-1)+i][(M-1)+j] = Lock[i][j];
            }
        }     
        
        for(int k=0;k<Board.length;k++){
            for(int h=0;h<Board[k].length;h++){
                System.out.print(" "+Board[k][h]);
            }
            System.out.println();
        }
        System.out.println();
        
        //반복문을 돌면서 각각 겹치는 구간 반복문을 모두 돕니다.
        for(int rotate=0;rotate<4;rotate++){
            
            for(int i=0;i< N + (M-1);i++){
                for(int j=0;j< N + (M-1) ;j++){
                    //simulate에서 Board의 lock부분이 모두 1인지 확인합니다.
                    if(simulate(i, j) == true){
                        
                        System.out.println("i:"+i+"j:"+j);
                        return true;
                    }
                }
            }
            rotateBoard();
        }
        
        
        return false;
    }
    
    public boolean simulate(int startrow, int startcol){
        //Board의 부분에 Key의 모든값을 다 더합니다.
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                Board[startrow+i][startcol+j] += Key[i][j];
            }
        }
 
        //Board의 자물쇠 부분이 모두 1인지 확인합니다.
        if(check() == true)
            return true;
 
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                Board[(M-1)+i][(M-1)+j] = Lock[i][j];
            }
        }     
     
        return false;
    }
    
    public boolean check(){
        int count = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                //0이거나 2이상이라면 바로 끝임.
                if(Board[i+(M-1)][j+(M-1)] != 1){
                    return false;   
                }
            }
        }
        
        return true;
    }
 
    public void rotateBoard(){
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                temp[i][j] = Key[i][j];
            }
        }
        
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                Key[j][M-i-1] = temp[i][j];
            }
        }
    }
}

 

 

기억해야할점

 

첫번째, 홈끼리 만나면 안되기에 lock[][]은 모두 1 이어야만합니다. (0 이거나 2, 3, 4, 1 초과인경우 돌기가 서로 만나기에 맞지 않습니다.)

-자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

if(newLock[i][j] == 0 || newLock[i][j] > 1){
    return false;
}
 
or
 
if(newLock[i][j] != 1){
    return false;
}

 

두번째 코드입니다.

class Solution {
    int[][] Key;
    int[][] Lock;
    int[][] newLock;
    int lockLength = 0;
    public boolean solution(int[][] key, int[][] lock) {
        newLock = new int[key.length + key.length + lock.length - 2][key.length + key.length + lock.length - 2];
        Key = key;
        Lock = lock;
        
        for(int i=0;i<lock.length;i++){
            for(int j=0;j<lock.length;j++){
                newLock[i+key.length-1][j+key.length-1] = lock[i][j];
            }
        }
        
        // for(int i=0;i<key.length + key.length + lock.length - 2; i++){
        //     for(int j=0;j<key.length + key.length + lock.length - 2; j++){
        //         System.out.print(" "+newLock[i][j]);
        //     }
        //     System.out.println();
        // }
        // System.out.println();
        
        
        //각회전방향마다 다 돌면서.
        
        for(int rotate=0;rotate<4;rotate++){
            rotatekey();
            
            for(int j=0;j<=newLock.length - Key.length; j++){
                // System.out.println("hekko?");
                for(int k=0;k<=newLock.length - Key.length; k++){
                    // System.out.println("hekko?");
                    
                    for(int h=0;h<Key.length;h++){
                        for(int q=0;q<Key.length;q++){
                            newLock[j+h][k+q] += Key[h][q];
                        }
                    }
                    // System.out.println("hekko?");
                    if(check() == true){
                        return true;
                    }
                    
                    for(int h=0;h<Key.length;h++){
                        for(int q=0;q<Key.length;q++){
                            newLock[j+h][k+q] -= Key[h][q];
                        }
                    }
                }
            }
            
        }
        
        
        return false;
    }
    
    void rotatekey(){
        int[][] newkey = new int[Key.length][Key.length];
        
        for(int i=0;i<Key.length;i++){
            for(int j=0;j<Key.length;j++){
                newkey[j][Key.length - 1 - i] = Key[i][j];
            }
        }
        Key = newkey;
        // for(int i=0;i<Key.length;i++){
        //     for(int j=0;j<Key.length;j++){
        //         System.out.print(" "+Key[i][j]);   
        //     }
        //     System.out.println();
        // }
        // System.out.println();
 
    }
    
    boolean check(){
        // for(int i=0;i<Key.length + Key.length + Lock.length - 2; i++){
        //     for(int j=0;j<Key.length + Key.length + Lock.length - 2; j++){
        //         System.out.print(" "+newLock[i][j]);
        //     }
        //     System.out.println();
        // }
        // System.out.println();
        
        for(int i=Key.length - 1;i < Key.length - 1 + Lock.length;i++){
            for(int j=Key.length - 1;j < Key.length - 1 + Lock.length; j++){
                if(newLock[i][j] == 0 || newLock[i][j] > 1){
                    return false;
                }
            }
        }
        return true;
    }
}

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[카카오 기출 문제]블록 이동하기 - 레벨 3, BFS  (1) 2023.01.06
[카카오 기출 문제]불량 사용자- 레벨 3, 해쉬 + 이중해쉬 + 순열 + 조합  (0) 2022.12.15
[카카오 기출 문제]합승 택시 요금- 레벨 3, 다익스트라 + 완전탐색 + 아이디어 + 그래프  (0) 2022.11.17
[카카오 기출 문제]광고 삽입- 레벨 3, 아이디어 + 윈도우 슬라이딩  (0) 2022.11.15
[카카오 기출 문제]다단계 칫솔 판매- 레벨 3, 링크드리스트 + 트리 + 노드  (0) 2022.11.13

+ Recent posts

티스토리툴바