[프로그래머스 Lv.2] 후보키(Java) - DFS와 비트마스크 두 가지 풀이

📌 핵심 요약

• 후보키 = 유일성 + 최소성 — 두 조건을 각각 독립된 메서드로 분리하면 코드가 정의를 그대로 옮긴 형태가 된다
• 크기가 작은 조합부터 검사해야 한다 — 최소성 판단은 이미 확정된 키가 있어야 성립하므로 순서가 곧 전제 조건이다
• DFS와 비트마스크 두 가지로 풀었다 — 컬럼이 8개뿐이라 어느 쪽이든 통과하며, 서로 다른 지점에서 명쾌하다

 

목차

1 문제 정리

Programmers #42890

2019 카카오 개발자 겨울 인턴십 / 후보키

1 ≤ 행 ≤ 20 · 1 ≤ 열 ≤ 8

난이도: Lv.2

릴레이션(표)이 문자열 2차원 배열로 주어진다. 이때 후보키가 될 수 있는 속성(컬럼) 조합의 개수를 구하는 문제다. 후보키는 아래 두 조건을 모두 만족해야 한다.

후보키의 두 조건

1. 유일성 — 그 컬럼들의 값으로 모든 행을 서로 구분할 수 있어야 한다
2. 최소성 — 컬럼 중 하나라도 빼면 유일성이 깨져야 한다. 즉 이미 후보키인 조합을 부분집합으로 포함하면 안 된다

예제 데이터

   

example — relation

//      col 0    col 1     col 2       col 3
// 행0   100      ryan      music       2
// 행1   200      apeach    math        2
// 행2   300      tube      computer    3
// 행3   400      con       computer    4
// 행4   500      muzi      music       3
// 행5   600      apeach    music       2

// {0}   → 코드번호가 전부 다르므로 유일성 만족. 후보키
// {1,2} → 이름+전공 조합이 전부 다르므로 후보키
// {0,2} → 유일하지만 {0}을 포함하므로 최소성 위반
// 답: 2

2 접근 방향 잡기

무엇의 조합인가

처음에는 “각 튜플별로 가능한 모든 조합을 탐색하면 되는가”라고 생각했는데, 조합의 대상을 잘못 잡은 것이었다. 후보키는 어떤 컬럼들을 묶을 것인가를 고르는 문제이고, 행은 그 조합이 조건을 만족하는지 검증하는 데 쓰이는 데이터다.

완전탐색이 가능한 규모인가

제약을 보면 열은 최대 8개다. 부분집합은 2⁸ − 1 = 255개에 불과하다. 행도 최대 20개이므로 조합마다 유일성을 확인해도 연산량이 수만 회 수준이다. 완전탐색으로 밀어붙여도 된다는 판단이 여기서 선다.

ℹ️

코드를 짜기 전에 규모부터

이 판단이 서야 이후 설계가 정해진다. 컬럼이 8개라는 사실이 “재귀로 전부 만들어도 된다”와 “정수 하나로 조합을 표현할 수 있다”는 두 선택지를 모두 열어준다.

순서가 곧 전제 조건이다

최소성은 “이미 확정된 후보키를 포함하지 않는가”로 판단한다. 그러려면 작은 조합이 먼저 확정되어 있어야 한다.

{0}을 먼저 후보키로 등록해야 {0,2}를 걸러낼 수 있다.

이 순서를 보장하는 방법은 두 가지다. 조합을 만드는 단계에서 크기를 1부터 올리거나, 만든 뒤 크기 순으로 정렬하거나. 아래 두 풀이는 각각 다른 쪽을 택했다.

3 풀이 1 — DFS와 백트래킹

바깥 for문에서 조합의 크기를 1부터 colCount까지 늘리고, 각 크기마다 DFS로 그 크기의 조합만 만든다. 크기 순 처리가 루프 구조로 드러나므로 별도 정렬이 필요 없다.

   

Java — DFS 풀이

import java.util.*;

class Solution {
    private int rowCount, colCount;
    private String[][] relation;
    private List<Set<Integer>> candidateKeys;   // 확정된 후보키

    public int solution(String[][] relation) {
        this.relation = relation;
        this.rowCount = relation.length;
        this.colCount = relation[0].length;
        this.candidateKeys = new ArrayList<>();

        // 컬럼 개수를 1개부터 늘려가며 탐색한다
        // 작은 조합이 먼저 확정되므로 최소성 가지치기가 성립한다
        for (int size = 1; size <= colCount; size++) {
            dfs(0, 0, size, new HashSet<>());
        }

        return candidateKeys.size();
    }

    /**
     * @param start       다음에 고를 수 있는 최소 컬럼 인덱스
     * @param depth       현재까지 고른 컬럼 개수
     * @param targetSize  이번 회차에 만들 조합의 크기
     * @param currentKey  현재까지 고른 컬럼 집합
     */
    private void dfs(int start, int depth, int targetSize, Set<Integer> currentKey) {
        // 최소성 검사 — 이미 확정된 후보키를 포함하면 이 가지는 버린다
        for (Set<Integer> key : candidateKeys) {
            if (currentKey.containsAll(key)) {
                return;
            }
        }

        // 목표 크기에 도달했으면 유일성만 확인하면 된다
        if (depth == targetSize) {
            if (isUnique(currentKey)) {
                candidateKeys.add(new HashSet<>(currentKey));   // 복사본
            }
            return;
        }

        // 오름차순으로만 컬럼을 골라 중복 조합을 방지한다
        for (int i = start; i < colCount; i++) {
            currentKey.add(i);
            dfs(i + 1, depth + 1, targetSize, currentKey);
            currentKey.remove(i);   // 백트래킹
        }
    }

    /** 이 컬럼 조합으로 모든 행이 서로 구분되는가 */
    private boolean isUnique(Set<Integer> keySet) {
        Set<String> rowSet = new HashSet<>();

        for (int r = 0; r < rowCount; r++) {
            StringBuilder sb = new StringBuilder();
            for (int col : keySet) {
                // 구분자를 넣어야 경계 정보가 보존된다
                sb.append(relation[r][col]).append("/");
            }
            rowSet.add(sb.toString());
        }

        // 중복 없이 모든 행이 서로 다른 문자열이면 유일성 만족
        return rowSet.size() == rowCount;
    }
}

start 인덱스로 중복 조합 차단

for (int i = start; ...)로 시작하고 다음 재귀에 i + 1을 넘기므로 항상 오름차순 조합만 만들어진다. {0,1}과 {1,0}이 따로 생기지 않는다.

   

trace — targetSize = 2, colCount = 4

dfs(start=0, depth=0)   currentKey = {}
 ├ i=0 → add(0)         currentKey = {0}
 │   dfs(start=1, depth=1)
 │    ├ i=1 → add(1)    currentKey = {0,1}  → depth==2, 검사
 │    │       remove(1) currentKey = {0}
 │    ├ i=2 → add(2)    currentKey = {0,2}  → 검사
 │    │       remove(2) currentKey = {0}
 │    └ i=3 → add(3)    currentKey = {0,3}  → 검사
 │            remove(3) currentKey = {0}
 │   remove(0)            currentKey = {}
 └ i=1 → ...

remove가 실행될 때마다 currentKey가 직전 상태로 정확히 돌아간다. 이 되돌리기가 백트래킹의 핵심이다.

가지치기 위치

최소성 검사를 재귀 진입 시점에 두었다. 종료 조건보다 앞에 있으므로 조합을 끝까지 만들기 전에 잘라낸다. {0}이 확정된 뒤 {0,1} 경로로 들어가는 순간 바로 되돌아 나오고, 그 아래 {0,1,2}, {0,1,3} 같은 가지가 통째로 사라진다.

4 풀이 2 — 비트마스크

컬럼이 8개이므로 조합을 정수 하나로 표현할 수 있다. 0부터 255까지의 수에서 켜진 비트가 곧 고른 컬럼이다. 재귀도 백트래킹도 필요 없어진다.

   

Java — 비트마스크 풀이

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int rowCount = relation.length;
        int colCount = relation[0].length;

        // 1단계: 모든 조합을 만들어 크기 순으로 정렬한다
        List<Integer> masks = new ArrayList<>();
        for (int mask = 1; mask < (1 << colCount); mask++) {
            masks.add(mask);
        }
        masks.sort(Comparator.comparingInt(Integer::bitCount));

        // 2단계: 유일성 + 최소성 검사
        List<Integer> keys = new ArrayList<>();

        for (int mask : masks) {
            // 최소성 — 이미 확정된 키를 통째로 포함하면 탈락
            boolean minimal = true;
            for (int key : keys) {
                if ((mask & key) == key) {
                    minimal = false;
                    break;
                }
            }
            if (!minimal) continue;

            // 유일성 — 선택된 컬럼 값을 이어붙여 중복 확인
            Set<String> seen = new HashSet<>();
            for (String[] row : relation) {
                StringBuilder sb = new StringBuilder();
                for (int col = 0; col < colCount; col++) {
                    if ((mask & (1 << col)) != 0) {
                        sb.append(row[col]).append("/");
                    }
                }
                seen.add(sb.toString());
            }

            if (seen.size() == rowCount) {
                keys.add(mask);
            }
        }

        return keys.size();
    }
}

알아야 할 연산은 세 가지뿐

연산	의미	대응되는 표현
1 << colCount	2의 colCount제곱	가능한 조합의 총 개수
(mask & (1 << col)) != 0	col번 비트가 켜져 있는가	set.contains(col)
(mask & key) == key	key의 모든 비트가 mask에도 있는가	set.containsAll(key)

세 번째가 핵심이다. key에서 켜진 비트가 mask에도 전부 켜져 있으면 and 결과가 key 그대로 남는다. 부분집합 판정을 정수 연산 하나로 끝내는 관용구다.

Integer.bitCount(mask)는 켜진 비트의 개수, 즉 조합의 크기를 돌려준다. 이것으로 정렬하면 크기 순 처리가 보장된다.

🚨

마스크 값 순서는 크기 순이 아니다

3(0b011, 크기 2)이 4(0b100, 크기 1)보다 작다. 정렬을 빼고 1부터 순서대로 훑으면 크기 2짜리가 크기 1짜리보다 먼저 검사되어 최소성 판단이 무너진다.

6 구분자가 필수인 이유

두 풀이 모두 값을 이어붙일 때 append("/")를 넣었다. 이어붙이기는 경계 정보를 잃는 연산이기 때문이다.

   

example — 구분자 유무의 차이

// 구분자 없음 — 서로 다른 행이 같은 문자열이 된다
행A: "ab" + "c"   → "abc"
행B: "a"  + "bc"  → "abc"   ← 중복으로 판정됨

// 구분자 있음 — 경계가 복원된다
행A: "ab/c/"
행B: "a/bc/"              ← 정상적으로 구분됨

이 문제의 값은 1~8자의 알파벳 소문자와 숫자이므로 위와 같은 데이터가 실제로 존재할 수 있다. 숫자만 있는 컬럼이라면 12 + 3과 1 + 23이 둘 다 "123"이 되는 식으로도 발생한다.

마지막 값 뒤에도 구분자가 붙어 "a/b/"처럼 끝나지만 문제되지 않는다. 모든 행이 같은 규칙으로 만들어지므로 비교에 영향이 없고, “마지막만 제외” 같은 분기를 넣지 않아도 되어 오히려 단순하다.

7 두 풀이 비교

구분	DFS + 백트래킹	비트마스크
메서드 개수	3개	1개
재귀	필요	불필요
크기 순 보장	바깥 for문 (구조로 표현)	bitCount 정렬
최소성 판정	containsAll	(mask & key) == key
가지치기	완성 전 차단 가능	조합 단위로만 건너뜀
실수 지점	remove, 복사본	없음
사전지식	불필요	비트 연산 이해 필요

“사전지식 없이 읽히는가”를 기준으로 하면 DFS가 낫다.

containsAll은 그대로 읽히지만 (mask & key) == key는 한 번 해석해야 한다.

ℹ️

비트마스크는 관용구다

부분집합을 다루는 문제에서 반복적으로 등장한다. 외판원 순회나 집합 DP 계열로 넘어가면 사실상 필수가 되므로, 컬럼이 8개로 작은 이 문제에서 두 방식을 나란히 두고 익혀두면 이후에 도움이 된다.

8 정리

항목	내용
조합 개수	28 − 1 = 255개 (열 8개 기준)
유일성 검사	조합당 20행 × 8컬럼
최소성 검사	조합당 최대 확정 키 개수만큼 비교
전체 연산량	수만 회 수준 — 완전탐색 가능

이 문제에서 어려웠던 부분은 알고리즘 자체가 아니라 조합의 대상을 무엇으로 잡을 것인가였다. 튜플을 조합하려 하면 방향이 어긋나고, 컬럼을 조합 대상으로 잡는 순간 나머지는 완전탐색으로 정리된다.

그리고 최소성이라는 조건이 탐색 순서에 제약을 건다는 점도 확인했다. 검사 로직만 옳게 짜면 되는 것이 아니라, 작은 조합이 먼저 확정되어야 그 검사가 의미를 갖는다.

조건과 순서가 얽혀 있는 문제였다고 판단했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.