Programmers - 후보키

---

title: Programmers - 후보키
date: 2022-06-24
tags:

• Algorithm
• DFS

---

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

문제 요약

테이블이 주어지며, 이를 이용하여 후보키를 찾는다. 후보키로 구성된 column들은 중복이 있어서는 안 되며, 해당 후보키의 구성들로 이루어진 조합 중 어느 것도 후보키가 되어서는 안 된다. 후보키의 개수를 return한다.

문제 풀이

개인적으로 좋아하지 않는 유형의 문제이기도 하고, 비트 연산을 사용하지 않아 많이 더러운 프로그램을 작성하게 되었다.
DFS 방식으로 문제를 풀었다. 첫 column부터 비교하며 후보키로 구성이 가능하다면 추가해준다. 후보키 여부에 상관 없이 해당 column을 제외하고 다음 column부터 다시 탐색을 시작한다.
각 DFS에서는 지금까지 찾은 columne들을 저장해야 하므로 .data 함수를 이용하여 데이터들을 포인터로 넘긴다. 이로 인해 NULL이 넘어올 수 있기에 처리를 해줘야 하며, DFS마다 새로운 데이터를 가지고 있어야 하기 때문에 불필요한 메모리 낭비가 크다.
문제 해결 후 비트 연산을 이용한 풀이를 확인하였으며, 비트 연산에 더욱 익숙해져야 한다는 것을 깨달았다.

프로그램

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using std :: string ;
using std :: vector ;
using std :: unordered_map ;

int iRowLen ;
int iColumnLen ;
vector < string > * vpOrigin ;
vector < string > vCandidate ;

bool bCompare ( string & str1 , string & str2 )
{
    return str1.size () < str2.size () ;
}

void DFS ( string * strpTemp , int iColumnIndex )
{
    vector < string > vpTemp ;
    bool bCandidate = true ;
    int iReturn = 0 ;


    if ( iColumnIndex == iColumnLen )                        // This is not candidate key
        return ;


    unordered_map < string , int > tempMap ;

    for ( int i = 0 ; i < iRowLen ; ++i )
    {
        vpTemp.emplace_back ( strpTemp [ i ] ) ;
        vpTemp [ i ] += vpOrigin [ i ] [ iColumnIndex ] ;

        if ( 2 == ++ tempMap [ vpTemp [ i ] ] )                // Add and check. If 2, then it's not candidate key
        {
            bCandidate = false ;
        }
    }

    vpTemp.emplace_back ( strpTemp [ iRowLen ] ) ;            // Store column list
    vpTemp [ iRowLen ] += iColumnIndex + 1 ;

    if ( bCandidate )
    {
        vCandidate.emplace_back ( vpTemp [ iRowLen ] ) ;
    }
    else
    {
        DFS ( vpTemp.data () , iColumnIndex + 1 ) ;            // Not found, keep finding
    }

    DFS ( strpTemp , iColumnIndex + 1 ) ;                    // Check candidate key except current column
}

int solution ( vector < vector < string > > relation )
{
    iRowLen = relation.size () ;
    iColumnLen = relation [ 0 ].size () ;
    vpOrigin = relation.data () ;
    string str ;

    str.resize ( iRowLen ) ;


    DFS ( NULL , 0 ) ;        // DFS


    std :: sort ( vCandidate.begin () , vCandidate.end () , bCompare ) ;
    int iCnt = 0 ;

    for ( int i = 0 ; i < vCandidate.size () ; ++i )        // Eliminate overlapped candidate key
    {
        for ( int j = 0 ; j < vCandidate.size () ; ++j )
        {
            if ( i == j )
                continue ;

            iCnt = 0 ;

            for ( int k = 0 ; k < vCandidate [ i ].size () ; ++k )
            {
                if ( string :: npos != vCandidate [ j ].find ( vCandidate [ i ] [ k ] ) )
                {
                    ++ iCnt ;
                }
            }

            if ( iCnt == vCandidate [ i ].size () )
            {
                vCandidate.erase ( vCandidate.begin () + j ) ;
                --j ;
            }
        }
    }

    return vCandidate.size () ;
}