Programmers - 자물쇠와 열쇠

---

title: Programmers - 자물쇠와 열쇠
date: 2022-08-08
tags:

• Algorithm

---

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

문제 요약

정사각형의 배열에 자물쇠와 열쇠의 정보가 주어진다.
열쇠의 일부분은 자물쇠의 범위 밖에 있어도 되나, 자물쇠의 빈 공간은 모두 열쇠로 채워져야만 lock이 풀린다.
주어진 열쇠로 주어진 자물쇠를 열 수 있는지 여부를 return한다.

문제 풀이

열쇠가 자물쇠의 범위 바깥으로 넘어갈 수 있으므로, 처음에는 문자열로 변환하여 처리를 할까 고민하였다.
하지만 최대 길이가 60일 때, 각 방향으로 최대 19씩 확장해야 하기에 총 58 x 58의 문자열을 이용하여야 한다.
범위 바깥의 문자열은 처리할 수 없기에 substr을 많이 사용하게 되며, overhead가 너무 커질 것이라 판단하였다.
이에 조금 더 머리를 써, 열쇠를 좌표로만 환산하여 사용하기로 결정하였다.


열쇠의 각 부분에 대한 x,y 좌표를 저장한다.
이 때 (0,0) 부터 (n-1,n-1) 까지의 좌표로 저장이 되어있을 것이다.
(n-1,n-1)이 (0,0)이 되는 범위부터 (0,0)이 (n-1,n-1)이 되는 범위까지 각 좌표들에 offset을 더해주어 비교를 한다.
자물쇠의 빈 부분의 개수를 세고, 각 offset을 이용하였을 때 자물쇠의 꽉 찬 부분에 걸리지 않고 빈 부분을 채운 개수를 count한다.
현재 열쇠의 배치로 이것이 불가능하다면 90도씩 회전하고, 위의 검사를 다시 진행한다.
360도 회전은 현재와 같으므로, 총 4번의 검사를 진행하며 중간에 true가 발견되면 바로 true를 return, 발견되지 않는다면 자물쇠를 열지 못 한다.

프로그램

#include <vector>
#include <utility>

using std :: vector ;
using std :: pair ;
using std :: make_pair ;

void rotateKey ( vector < pair < int , int > > & vKey , int iKeySize )            // Rotate 90 degree to counterclock
{
    int iKeyCount = vKey.size () ;



    for ( int i = 0 ; i < iKeyCount ; ++i )
    {
        pair < int , int > pTemp = vKey [ i ] ;
        vKey [ i ] = make_pair ( iKeySize - pTemp.second - 1 , pTemp.first ) ;
    }
}

bool bIsKeyFitToLock ( vector < pair < int , int > > & vKey , vector < vector < int > > & vLock , int iLockCount , int iKeySize )
{
    int iKeyCount = vKey.size () ;
    int iLockSize = vLock.size () ;
    int iKeyFitCount = 0 ;



    for ( int i = - iKeySize + 1 ; i < iLockSize ; ++i )
    {
        for ( int j = - iKeySize + 1 ; j < iLockSize ; ++j )
        {
            iKeyFitCount = 0 ;


            for ( int k = 0 ; k < iKeyCount ; ++k )
            {
                int iX = vKey [ k ].first + i ;
                int iY = vKey [ k ].second + j ;

                if ( ( iX < 0 ) || ( iY < 0 ) || ( iLockSize <= iX ) || ( iLockSize <= iY ) )
                    continue ;

                if ( 1 == vLock [ iX ] [ iY ] )
                    break ;

                ++ iKeyFitCount ;
            }

            if ( iLockCount == iKeyFitCount )
                return true ;
        }
    }


    return false ;
}

bool solution ( vector < vector < int > > key , vector < vector < int > > lock )
{
    int iKeySize = key.size () ;
    int iLockSize = lock.size () ;
    int iLockCount = 0 ;
    vector < pair < int , int > > vKeyCoordinate ;



    for ( int i = 0 ; i < iKeySize ; ++i )
    {
        int * ipTemp = key [ i ].data () ;

        for ( int j = 0 ; j < iKeySize ; ++j )
        {
            if ( 1 == * ipTemp ++ )
            {
                vKeyCoordinate.emplace_back ( make_pair ( i , j ) ) ;
            }
        }
    }
    for ( int i = 0 ; i < iLockSize ; ++i )
    {
        int * ipTemp = lock [ i ].data () ;

        for ( int j = 0 ; j < iLockSize ; ++j )
        {
            if ( 0 == * ipTemp ++ )
            {
                ++ iLockCount ;
            }
        }
    }

    for ( int i = 0 ; i < 4 ; ++i )
    {
        if ( bIsKeyFitToLock ( vKeyCoordinate , lock , iLockCount , iKeySize ) )
            return true ;

        rotateKey ( vKeyCoordinate , iKeySize ) ;
    }


    return false ;
}