프로그래머스 후보키

후보키 : programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

이전 게시글에서 비트 마스크로 조합을 만들어 보았다.

바로 이문제를 위해서 비트 마스크를 업로드 했던것이다^^

2차원 배열이 주어질때 후보키가 될수 있는 가짓수를 구하는 문제였는데

Set과 비트마스크를 이용한 조합을 사용하면 금방 뚝딱 풀 수 있다.

import java.util.*;
class Solution {
    public List<Integer> list = new ArrayList<Integer>();

	public int solution(String[][] relation) {
		int  cLen = relation.length, rLen = relation[0].length;
		for (int i = 1; i < (1 << rLen); i++) {
			if (gazichigi(i)) {
				continue;
			}
			if (combi(i, cLen, rLen, relation)) {
				list.add(i);
			}

		}
		return list.size();
	}

	public boolean gazichigi(int i) {
		for (int element : list) {
			if ((element & i) == element) {
				return true;
			}
		}
		return false;
	}

	public Set<String> set = new HashSet<String>();

	public boolean combi(int i, int cLen, int rLen, String[][] relation) {
		StringBuilder sb = new StringBuilder();
        set.clear();
		for (int cl = 0; cl < cLen; cl++) {
			sb.setLength(0);

			for (int rl = 0; rl < rLen; rl++) {
				if ((i & (1 << rl)) != 0) {
					sb.append(relation[cl][rl]);
				}
			}
			if (set.contains(sb.toString())) {
				return false;
			} else {
				set.add(sb.toString());
			}
		}
		return true;
	}

}