λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Algorithm

πŸ˜„ 2019 카카였 λΈ”λΌμΈλ“œ 곡채: 후보킀 (Java)

πŸ“Œ λ¬Έμ œ

ν”„λ Œμ¦ˆλŒ€ν•™κ΅ 컴퓨터곡학과 쑰ꡐ인 μ œμ΄μ§€λŠ” λ„€μ˜€ ν•™κ³Όμž₯λ‹˜μ˜ μ§€μ‹œλ‘œ, ν•™μƒλ“€μ˜ 인적사항을 μ •λ¦¬ν•˜λŠ” 업무λ₯Ό λ‹΄λ‹Ήν•˜κ²Œ λ˜μ—ˆλ‹€.

그의 ν•™λΆ€ μ‹œμ ˆ ν”„λ‘œκ·Έλž˜λ° κ²½ν—˜μ„ λ˜μ‚΄λ €, λͺ¨λ“  인적사항을 λ°μ΄ν„°λ² μ΄μŠ€μ— λ„£κΈ°λ‘œ ν•˜μ˜€κ³ , 이λ₯Ό μœ„ν•΄ 정리λ₯Ό ν•˜λ˜ 쀑에 후보킀(Candidate Key)에 λŒ€ν•œ 고민이 ν•„μš”ν•˜κ²Œ λ˜μ—ˆλ‹€.

후보킀에 λŒ€ν•œ λ‚΄μš©μ΄ 잘 κΈ°μ–΅λ‚˜μ§€ μ•Šλ˜ μ œμ΄μ§€λŠ”, μ •ν™•ν•œ λ‚΄μš©μ„ νŒŒμ•…ν•˜κΈ° μœ„ν•΄ λ°μ΄ν„°λ² μ΄μŠ€ κ΄€λ ¨ μ„œμ μ„ ν™•μΈν•˜μ—¬ μ•„λž˜μ™€ 같은 λ‚΄μš©μ„ ν™•μΈν•˜μ˜€λ‹€.

  • 관계 λ°μ΄ν„°λ² μ΄μŠ€μ—μ„œ λ¦΄λ ˆμ΄μ…˜(Relation)의 νŠœν”Œ(Tuple)을 μœ μΌν•˜κ²Œ 식별할 수 μžˆλŠ” 속성(Attribute) λ˜λŠ” μ†μ„±μ˜ 집합 쀑, λ‹€μŒ 두 μ„±μ§ˆμ„ λ§Œμ‘±ν•˜λŠ” 것을 후보 ν‚€(Candidate Key)라고 ν•œλ‹€.
    • μœ μΌμ„±(uniqueness) : λ¦΄λ ˆμ΄μ…˜μ— μžˆλŠ” λͺ¨λ“  νŠœν”Œμ— λŒ€ν•΄ μœ μΌν•˜κ²Œ μ‹λ³„λ˜μ–΄μ•Ό ν•œλ‹€.
    • μ΅œμ†Œμ„±(minimality) : μœ μΌμ„±μ„ 가진 ν‚€λ₯Ό κ΅¬μ„±ν•˜λŠ” 속성(Attribute) 쀑 ν•˜λ‚˜λΌλ„ μ œμ™Έν•˜λŠ” 경우 μœ μΌμ„±μ΄ κΉ¨μ§€λŠ” 것을 μ˜λ―Έν•œλ‹€. 즉, λ¦΄λ ˆμ΄μ…˜μ˜ λͺ¨λ“  νŠœν”Œμ„ μœ μΌν•˜κ²Œ μ‹λ³„ν•˜λŠ” 데 κΌ­ ν•„μš”ν•œ μ†μ„±λ“€λ‘œλ§Œ κ΅¬μ„±λ˜μ–΄μ•Ό ν•œλ‹€.

μ œμ΄μ§€λ₯Ό μœ„ν•΄, μ•„λž˜μ™€ 같은 ν•™μƒλ“€μ˜ 인적사항이 μ£Όμ–΄μ‘Œμ„ λ•Œ, 후보 ν‚€μ˜ μ΅œλŒ€ 개수λ₯Ό κ΅¬ν•˜λΌ.

μœ„μ˜ 예λ₯Ό μ„€λͺ…ν•˜λ©΄, ν•™μƒμ˜ 인적사항 λ¦΄λ ˆμ΄μ…˜μ—μ„œ λͺ¨λ“  학생은 각자 μœ μΌν•œ ν•™λ²ˆμ„ 가지고 μžˆλ‹€. λ”°λΌμ„œ ν•™λ²ˆμ€ λ¦΄λ ˆμ΄μ…˜μ˜ 후보 ν‚€κ°€ 될 수 μžˆλ‹€.
κ·Έλ‹€μŒ μ΄λ¦„에 λŒ€ν•΄μ„œλŠ” 같은 이름(apeach)을 μ‚¬μš©ν•˜λŠ” 학생이 있기 λ•Œλ¬Έμ—, μ΄λ¦„은 후보 ν‚€κ°€ 될 수 μ—†λ‹€. κ·ΈλŸ¬λ‚˜, λ§Œμ•½ [이름, μ „곡]을 ν•¨κ»˜ μ‚¬μš©ν•œλ‹€λ©΄ λ¦΄λ ˆμ΄μ…˜μ˜ λͺ¨λ“  νŠœν”Œμ„ μœ μΌν•˜κ²Œ 식별 κ°€λŠ₯ν•˜λ―€λ‘œ 후보 ν‚€κ°€ 될 수 있게 λœλ‹€.
λ¬Όλ‘  [이름, μ „곡, ν•™λ…„]을 ν•¨κ»˜ μ‚¬μš©ν•΄λ„ λ¦΄λ ˆμ΄μ…˜μ˜ λͺ¨λ“  νŠœν”Œμ„ μœ μΌν•˜κ²Œ 식별할 수 μžˆμ§€λ§Œ, μ΅œμ†Œμ„±μ„ λ§Œμ‘±ν•˜μ§€ λͺ»ν•˜κΈ° λ•Œλ¬Έμ— 후보 ν‚€κ°€ 될 수 μ—†λ‹€.
λ”°λΌμ„œ, μœ„μ˜ 학생 μΈμ μ‚¬ν•­μ˜ ν›„λ³΄ν‚€λŠ” ν•™λ²ˆ, [이름, μ „곡] 두 κ°œκ°€ λœλ‹€.

λ¦΄λ ˆμ΄μ…˜μ„ λ‚˜νƒ€λ‚΄λŠ” λ¬Έμžμ—΄ λ°°μ—΄ relation이 λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 이 λ¦΄λ ˆμ΄μ…˜μ—μ„œ 후보 ν‚€μ˜ 개수λ₯Ό return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•˜λΌ.

πŸ“Œ μ œν•œμ‚¬ν•­

  • relation은 2차원 λ¬Έμžμ—΄ 배열이닀.
  • relation의 컬럼(column)의 κΈΈμ΄λŠ” 1 μ΄μƒ 8 μ΄ν•˜μ΄λ©°, 각각의 μ»¬λŸΌμ€ λ¦΄λ ˆμ΄μ…˜μ˜ 속성을 λ‚˜νƒ€λ‚Έλ‹€.
  • relation의 둜우(row)의 κΈΈμ΄λŠ” 1 μ΄μƒ 20 μ΄ν•˜μ΄λ©°, 각각의 λ‘œμš°λŠ” λ¦΄λ ˆμ΄μ…˜μ˜ νŠœν”Œμ„ λ‚˜νƒ€λ‚Έλ‹€.
  • relation의 λͺ¨λ“  λ¬Έμžμ—΄μ˜ κΈΈμ΄λŠ” 1 μ΄μƒ 8 μ΄ν•˜μ΄λ©°, μ•ŒνŒŒλ²³ μ†Œλ¬Έμžμ™€ 숫자둜만 이루어져 μžˆλ‹€.
  • relation의 λͺ¨λ“  νŠœν”Œμ€ μœ μΌν•˜κ²Œ 식별 κ°€λŠ₯ν•˜λ‹€.(즉, μ€‘λ³΅λ˜λŠ” νŠœν”Œμ€ μ—†λ‹€.)

πŸ“Œ ν’€μ΄

문제λ₯Ό μ œλŒ€λ‘œ μ΄ν•΄ν•˜μ§€ λͺ»ν•΄μ„œ μ‹œκ°„μ΄ κ±Έλ Έμ—ˆλ‹€. μ—¬κΈ°μ„œ κ°€μž₯ μ€‘μš”ν•œ 것은 ν›„λ³΄ν‚€μ˜ 쑰건이닀.

1. μœ μΌμ„±μ„ λ§Œμ‘±ν•  것.
λͺ¨λ“  νŠœν”Œμ΄ μœ μΌν•΄μ•Ό ν•œλ‹€. 즉, λͺ¨λ“  후보킀에 ν•΄λ‹Ήν•˜λŠ” νŠœν”Œμ΄ 쀑볡이 μ—†μ–΄μ•Ό ν•œλ‹€.

2. μ΅œμ†Œμ„±μ„ λ§Œμ‘±ν•  것.
ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€μ—μ„œλŠ” μ•„λž˜μ™€ 같이 μ„€λͺ…ν–ˆλ‹€.
μœ μΌμ„±μ„ 가진 ν‚€λ₯Ό κ΅¬μ„±ν•˜λŠ” 속성(Attribute) 쀑 ν•˜λ‚˜λΌλ„ μ œμ™Έν•˜λŠ” 경우 μœ μΌμ„±μ΄ κΉ¨μ§€λŠ” 것을 μ˜λ―Έν•œλ‹€. 즉, λ¦΄λ ˆμ΄μ…˜μ˜ λͺ¨λ“  νŠœν”Œμ„ μœ μΌν•˜κ²Œ μ‹λ³„ν•˜λŠ” 데 κΌ­ ν•„μš”ν•œ μ†μ„±λ“€λ‘œλ§Œ κ΅¬μ„±λ˜μ–΄μ•Ό ν•œλ‹€.
μ΅œμ†Œμ„±μ„ μ œλŒ€λ‘œ μ΄ν•΄ν•˜μ§€ λͺ»ν•˜κ³ , 문제λ₯Ό ν’€μ–΄λ³΄λ‹ˆ 계속 ν…ŒμŠ€νŠΈμ— μ‹€νŒ¨..

μ΅œμ†Œμ„±μ€ λΆ€λΆ„ 집합이 μ‘΄μž¬ν•œλ‹€λ©΄ λ§Œμ‘±ν•˜μ§€ λͺ»ν•œλ‹€. 예λ₯Ό λ“€μ–΄ μœ μΌμ„±μ„ λ§Œμ‘±ν•˜λŠ” [A, B], [A, B, C]κ°€ μžˆλ‹€κ³  κ°€μ •ν•œλ‹€. [A, B]κ°€ [A, B, C]의 λΆ€λΆ„ 집합이기 λ•Œλ¬Έμ— [A, B, C]λŠ” μ΅œμ†Œμ„±μ„ λ§Œμ‘±ν•˜μ§€ λͺ»ν•œλ‹€. λ”°λΌμ„œ 후보킀가 될 수 μžˆλŠ” 것은 [A, B] 이닀.

λ¨Όμ € dfs둜 크기가 μž‘μ€ μˆœμ„œλŒ€λ‘œ 컬럼의 쑰합듀을 κ΅¬ν–ˆλ‹€.

μœ μΌμ„±μ„ μ²΄ν¬ν•˜κΈ° μœ„ν•΄ Set을 μ΄μš©ν–ˆλ‹€. λͺ¨λ“  νŠœν”Œμ„ λŒλ©΄μ„œ 컬럼의 쑰합에 ν•΄λ‹Ήν•˜λŠ” νŠœν”Œλ“€μ„ λ½‘μ•„λƒˆλ‹€. μ΄λ•Œ 쀑볡이 μžˆλ‹€λ©΄ μœ μΌμ„±μ„ λ§Œμ‘±ν•˜μ§€ λͺ»ν•˜λŠ” 것과 κ°™κΈ° λ•Œλ¬Έμ— λ‹€μŒ 둜직으둜 λ„˜μ–΄κ°€μ§€ λͺ»ν•˜λ„둝 ν–ˆλ‹€.

μ—¬κΈ°κΉŒμ§€ λ„˜μ–΄μ™”λ‹€λ©΄ μœ μΌμ„±μ„ λͺ¨λ‘ ν†΅κ³Όν•œ 컬럼의 μ‘°ν•©μ΄λΌλŠ” λœ»μ΄λ‹€.

이제 μ΅œμ†Œμ„±μ„ ν™•μΈν•œλ‹€. λΆ€λΆ„ 집합을 κ΅¬ν•˜κΈ° μœ„ν•΄ λΉ„νŠΈλ₯Ό μ΄μš©ν–ˆλ‹€. λΉ„νŠΈλ‘œ ν‘œν˜„ν•˜λ©΄ 0110κ³Ό 0111으둜 λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€. 0110이 0111의 λΆ€λΆ„ 집합인지 νŒλ‹¨ν•˜κΈ° μœ„ν•΄ 0110의 1이 0111에 λͺ¨λ‘ ν¬ν•¨λ˜λŠ”μ§€ ν™•μΈν•˜λ©΄ λœλ‹€. λ§Œμ•½μ—  λͺ¨λ‘ 포함이 μ•ˆλœλ‹€λ©΄ candidates에 λ„£μœΌλ©΄ λœλ‹€.

λ§ˆμ§€λ§‰μœΌλ‘œ λͺ¨λ“  후보킀λ₯Ό κ΅¬ν•˜λ©΄ κ·ΈλŒ€λ‘œ candidates의 μ‚¬μ΄μ¦ˆλ₯Ό λ¦¬ν„΄ν•˜λ©΄ ν•΄κ²° ν•  수 μžˆλŠ” λ¬Έμ œμ΄λ‹€.

πŸ“Œ μ½”λ“œ

import java.util.*;

public class 후보킀 {

    String[][] relation;
    int colSize;
    boolean[] select;
    List<int[]> candidates = new ArrayList<>();

    public int solution(String[][] relation) {
        this.relation = relation;
        this.colSize = relation[0].length;
        this.select = new boolean[colSize];
        for (int i = 0; i < colSize; i++) {
            dfs(0, 0, i + 1);
        }
        return candidates.size();
    }

    private void dfs(int idx, int cnt, int selectSize) {
        if (cnt == selectSize) {
            List<Integer> tempColumns = new ArrayList<>();
            for (int i = 0; i < colSize; i++) {
                if (select[i]) tempColumns.add(i);
            }
            if (!isUnique(tempColumns)) return;

            int[] candidate = new int[colSize + 1];
            for (Integer col : tempColumns) {
                candidate[col] = 1;
                candidate[colSize]++;
            }
            add(candidate);
        }
        for (int i = idx; i < colSize; i++) {
            if (select[i]) continue;
            select[i] = true;
            dfs(i, cnt + 1, selectSize);
            select[i] = false;
        }
    }

    private boolean isUnique(List<Integer> columns) {
        Set<String> tempTuples = new HashSet<>();
        for (String[] tuple : relation) {
            StringBuilder sb = new StringBuilder();
            for (Integer col : columns) {
                sb.append(tuple[col]);
            }
            if (!tempTuples.add(sb.toString())) return false;
        }
        return true;
    }

    private void add(int[] requestCandidate) {
        for (int[] candidate : candidates) {
            int cnt = 0;
            for (int i = 0; i < requestCandidate.length - 1; i++) {
                if ((candidate[i] & requestCandidate[i]) == 1) cnt++;
                if (candidate[colSize] == cnt) return;
            }
        }
        this.candidates.add(requestCandidate);
    }
}

 

 

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€

μ½”λ“œ μ€‘μ‹¬μ˜ 개발자 μ±„μš©. μŠ€νƒ 기반의 ν¬μ§€μ…˜ 맀칭. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€μ˜ 개발자 λ§žμΆ€ν˜• ν”„λ‘œν•„μ„ λ“±λ‘ν•˜κ³ , λ‚˜μ™€ 기술 ꢁ합이 잘 λ§žλŠ” 기업듀을 맀칭 λ°›μœΌμ„Έμš”.

programmers.co.kr