[프로그래머스][C++] 후보키 (243)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

우선 맨 처음 문제를 보고 든 생각은 조합을 구해야 한다는 점이었다.

C++에서는 Python과 같이 조합을 구해주는 라이브러리가 없기 때문에 직접 구현해야 한다.

 

C++에서 조합을 구하는 방식은 크게 2가지이다.

1) DFS를 활용한 방식

2) 비트 마스킹 활용

 

이번 문제에서는 비트 마스킹을 적용하였다.

 

처음에만 어렵지 비트마스킹을 통해 조합을 구하는 방식은 어느 정도 암기하면 편하다.

다음은 해당 내용을 예전이 정리해둔 글이다 먼저 읽어보길 권장한다.

https://blogshine.tistory.com/123

[알고리즘] 비트마스크 조합, 부분수열

 

따라서 다음과 같이 for문을 도는 코드를 통해 조합을 구할 수 있다.

for(int i = 1; i < (1 << colLen); i++) {
    set<string> store;
    
    for(int j = 0; j < rowLen; j++) {
        string temp;
        for(int k = 0; k < colLen; k++) {
            if((i & (1 << k))) {
                temp += relation[j][k];
            }
        }
        store.insert(temp);
    }

    // 생략...
}

조금 더 살펴보자.

 

우리에게 가능한 조합의 경우는 1부터 ~ (1 << colLen) 미만까지 가능하다.

만약 colLen이 4라면 0001부터 0010, 0011, 0100, 0101, ..., 1111, 10000(2진수, 10진수로는 16) 미만까지 가능한 것이다.

따라서 첫 for문은 조합을 구하는 과정이다.

 

두 번째 for문은 모든 튜플을 살펴보기 위한 과정이다.

2차원 배열에서 세로 길이만큼 돌면서 모든 튜플을 확인한다.

이때 선택된 칸의 문자열들을 모두 합한다.

 

이후 set에 저장하여 set의 사이즈가 세로의 길이와 동일하다면, 이는 중복이 없다는 의미이다.

따라서 후보 키가 될 수도 있다. 다만 아직 최소성을 만족할지는 모른다.

 

세 번째 for문은 내부에서 1을 쉬프트 연산하면서 &연산을 통해 선택된 문자열을 구하는 과정이다.

 

마지막으로 최소성을 만족하는지 확인하는 과정은 다음과 같다.

최소성을 어떻게 확인해야 할까 고민하다, 다른 분들의 풀이를 참고하게 되었다.

다음 방식이 가장 깔끔한 방식인 것 같다.

vector<int> ans;

bool isUnique(int i) {
    int ansLen = ans.size();
    for(int n = 0; n < ansLen; n++) {
        if((ans[n] & i) == ans[n]) {
            return false;      
        }
    }
    return true;
}

이 또한 &연산을 통해 이전에 ans에 저장돼 있는 조합을 포함하는지 확인하게 된다.

이전 조합을 포함하지 않아야만 최소성을 만족시킬 수 있다.

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> ans;

bool isUnique(int i) {
    int ansLen = ans.size();
    for(int n = 0; n < ansLen; n++) {
        if((ans[n] & i) == ans[n]) {
            return false;      
        }
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    int rowLen = relation.size();
    int colLen = relation[0].size();
    
    for(int i = 1; i < (1 << colLen); i++) {
        set<string> store;
        for(int j = 0; j < rowLen; j++) {
            string temp;
            for(int k = 0; k < colLen; k++) {
                if((i & (1 << k))) {
                    temp += relation[j][k];
                }
            }
            store.insert(temp);
        }
        
        if(store.size() == rowLen) {
            if(isUnique(i)) {
                ans.push_back(i);
            }
        }
    
    }
    
    return ans.size();
}