Programmers - 캠핑

---

title: Programmers - 캠핑
date: 2022-09-22
tags:

• Algorithm
• DP

---

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

문제 요약

2차원 격자에 쐐기가 박혀있으며, 두 쐐기를 대각선으로 하여 텐트를 설치할 수 있다. 직사각형 형태로만 배치가 가능하다.
이 때 텐트의 경계를 제외한 안쪽 공간에 쐐기가 있다면 텐트를 설치할 수 없다.
설치 가능한 쐐기 쌍의 모든 경우의 수를 return한다.

문제 풀이

솔직히 좀 짜증나는 문제이다.
우선 직사각형으로만 배치해야 되는 것은, 텐트를 애매한 각도로 돌리면(90도 단위가 아닌 경우) 처리가 너무 많아지고 기하학 문제가 되어버린다.
최대 5K이고, 모든 쐐기쌍을 brute force로 비교하면 125G가 되어버린다.
물론 저보다 훨씬 낮은 횟수의 검사만 진행되겠지만, O(n^3) 알고리즘을 기대하고 낸 문제는 아니라고 판단하였다.
결국 이는 각 쌍을 이용할 때 바로 쐐기의 존재 유무를 파악할 수 있어야 한다는 뜻이다.
그렇다면 모든 쐐기의 정보가 저장이 되어 있으며, 이를 바로 추출할 수 있어야 하며, 이는 DP 문제임을 알 수 있다.
(x,y)까지의 쐐기의 개수를 저장하는 DP를 이용하면 약간의 연산을 통해 두 쐐기 사이의 쐐기 개수를 구할 수 있다.
문제는 범위가 2^31이라는 것이다. 최대 5K이지만 범위는 매우 넓다.
이는 넓은 범위에 들어오는 정보를 다룰 수 있는 공간에 집어넣어야 하는 것이며, 결국 좌표를 상대적으로 바라보면 해결할 수 있다.


두 축으로 나누어 좌표를 저장한 후, 이를 정렬하여 0이 아닌 위치에 있을 경우 상대 위치로 변환한다.
이 과정에서 unordered_map을 이용하여 빠르게 위치를 지정할 수 있다.
이후 모든 점을 순회하며 DP 배열에 추가해주며, 모든 위치를 저장하였다면 이를 한 꼭지점을 향하여 값을 누적하여 DP 배열을 온전히 만든다.
마지막으로 모든 점의 pair를 비교하며, 두 점 사이에 쐐기가 존재하면 1씩 값을 더해준다.
이 때 x,y 중 하나라도 같다면 한 면의 길이가 0이 되기에 쐐기를 배치할 수 없다.
x값 혹은 y값 끼리의 차이가 1이라면 내부 공간이 없기에 바로 추가해준다.
(iMinX,iMinY) , (iMaxX,iMaxY) 사이에 존재하는 쐐기의 개수는 다음과 같이 구할 수 있다.

DP [ iMaxX - 1 ] [ iMaxY - 1 ] - DP [ iMinX ] [ iMaxY - 1 ] - DP [ iMaxX - 1 ] [ iMinY ] + DP [ iMinX ] [ iMinY ]

그림으로 그려 영역으로 확인하면 위 식을 통해 경계를 제외한 내부 공간만 남는 것을 확인할 수 있다.
최종적으로 약 5.7s의 성능으로 해결할 수 있었으며, 최적화 작업을 어떻게 해야할지는 감이 잡히지 않는다.


카카오에서는 알고리즘 능력을 기본으로 하되, 다른 추가적인 능력을 요구할 때가 많다.
본 문제는 데이터에서 필요한 정보만 뽑아낼 수 있는 능력을 요구로 한다.
이를 알 수 없다면 좌표를 상대적으로 바라볼 수 없으며, 이 때문에 DP를 사용할 수 없다.
이로 인해 O(n^3) 알고리즘을 사용하여 문제를 풀 수 있으나, TLE 혹은 안 좋은 성능의 알고리즘으로 구현할 가능성이 높다.

프로그램

#include <vector>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using std :: vector ;
using std :: max ;
using std :: min ;
using std :: sort ;
using std :: unordered_map ;

int solution ( int n , vector < vector < int > > data )
{
    int answer = 0 ;
    int iDataSize = data.size () ;
    vector < int > vCompressX ;
    vector < int > vCompressY ;
    unordered_map < int , int > umCompressX ;
    unordered_map < int , int > umCompressY ;
    int iMaxX = 0 ;
    int iMaxY = 0 ;


    for ( int i = 0 ; i < iDataSize ; ++i )                // Add X,Y to vector
    {
        vCompressX.emplace_back ( data [ i ] [ 0 ] ) ;
        vCompressY.emplace_back ( data [ i ] [ 1 ] ) ;
    }

    sort ( vCompressX.begin () , vCompressX.end () ) ;
    sort ( vCompressY.begin () , vCompressY.end () ) ;
    sort ( data.begin () , data.end () , [] ( vector < int > & a , vector < int > & b )     // Sort origin coordinate
                                            {
                                                if ( a [ 0 ] < b [ 0 ] )
                                                    return true ;
                                                else if ( a [ 0 ] == b [ 0 ] )
                                                    return a [ 1 ] < b [ 1 ] ;
                                                else
                                                    return false ;
                                            } ) ;

    for ( int i = 0 ; i < iDataSize ; ++i )                // Compres X,Y
    {
        if ( ( 0 != vCompressX [ i ] ) && ( 0 == umCompressX [ vCompressX [ i ] ] ) )
        {
            umCompressX [ vCompressX [ i ] ] = ++ iMaxX ;
        }
        if ( ( 0 != vCompressY [ i ] ) && ( 0 == umCompressY [ vCompressY [ i ] ] ) )
        {
            umCompressY [ vCompressY [ i ] ] = ++ iMaxY ;
        }
    }

    vector < vector < int > > vDP ( iMaxX + 1 , vector < int > ( iMaxY + 1 , 0 ) ) ;

    for ( int i = 0 ; i < iDataSize ; ++i )                // Add compressed coordinate
    {
        int iX = data [ i ] [ 0 ] ;
        int iY = data [ i ] [ 1 ] ;

        ++ vDP [ umCompressX [ iX ] ] [ umCompressY [ iY ] ] ;
    }

    for ( int i = 0 ; i <= iMaxX ; ++i )                // Change coordinate to DP
    {
        for ( int j = 0 ; j < iMaxY ; ++j )
        {
            vDP [ i ] [ j + 1 ] += vDP [ i ] [ j ] ;
        }
    }
    for ( int j = 0 ; j <= iMaxY ; ++j )
    {
        for ( int i = 0 ; i < iMaxX ; ++i )
        {
            vDP [ i + 1 ] [ j ] += vDP [ i ] [ j ] ;
        }
    }


    for ( int i = 0 ; i < iDataSize - 1 ; ++i )            // Find if can place tent with every pair
    {
        int iMinX = umCompressX [ data [ i ] [ 0 ] ] ;

        for ( int j = i + 1 ; j < iDataSize ; ++j )
        {
            int iMaxX = umCompressX [ data [ j ] [ 0 ] ] ;
            int iMaxY = max ( umCompressY [ data [ i ] [ 1 ] ] , umCompressY [ data [ j ] [ 1 ] ] ) ;
            int iMinY = min ( umCompressY [ data [ i ] [ 1 ] ] , umCompressY [ data [ j ] [ 1 ] ] ) ;


            if ( ( iMaxX == iMinX ) || ( iMaxY == iMinY ) )
                continue ;

            if ( ( iMaxX + 1 == iMinX ) || ( 1 == abs ( iMaxY - iMinY ) ) )
                ++ answer ;
            else if ( 0 == vDP [ iMaxX - 1 ] [ iMaxY - 1 ] - vDP [ iMinX ] [ iMaxY - 1 ] - vDP [ iMaxX - 1 ] [ iMinY ] + vDP [ iMinX ] [ iMinY ] )
                ++ answer ;
        }
    }


    return answer ;
}