문제 출처
나의 풀이 (26.8/100, 실패)
문제 이해를 제대로 못했다.
조합으로 경우의 수를 구했어야 했는데, 그게 아니라 연속된 경우의 수만 구하다 보니(relation[i].slice(idx, j))
=> 심지어 단순 조합보다는 부분집합 개념을 사용해야 했다.
index 기준으로 01 012 0123 12 13 이렇게는 구했지만 13 14 처럼 연속되지 않는 경우의 수를 고려하지 못했다.
function solution(relation) {
let cnt = 0;
let idx = 0;
while (1) {
if (idx > relation[0].length - 1) break;
let flag = false;
let j = idx + 1;
while (1) {
if (j-idx > relation[0].length) break;
flag = true;
let tmp = [];
for (let i = 0; i < relation.length; i++) {
tmp.push(relation[i].slice(idx, j).join(""));
}
for (let i = 0; i < tmp.length; i++) {
for (let j = 0; j < tmp.length; j++) {
if (i === j) continue;
if (tmp[j] === tmp[i]) flag = false;
if (!flag) break;
}
if (!flag) break;
}
if (!flag) j++;
else if (flag) break;
}
// console.log(idx, j, flag);
if (flag) cnt++;
idx++;
}
return cnt;
}다른 풀이
유일성 : 각 요소 중 겹치는 게 있는지
최소성 : 포함하는 순간 break
// 1.
학생들의 인적사항을 index로 가정하고 배열을 만든다.
idxArr = [0, 1, 2, ...]
// 2.
조합을 구한다.
i를 사용해서 몇개를 조합할지 선택한다.
combinations에는 인적사항 index 조합이 들어가게 된다.
01, 02, 03, ..., 12, 13, 14, ...
// 3.
set를 사용해서 일회성을 체크한다.
set에 조합 index와 주어지는 relation을 조합해서 add한다.
전부 add한 뒤에, 겹치는 게 없다면 relation.length와 set.size가 같을 것이고, 겹치는 게 하나라도 있다면 둘의 길이가 같아질 수 없다.
둘의 길이가 같을 때가 일회성에 해당되므로 이걸 combinations에 담는다.
// 4.
최소성을 체크한다.
reduce를 사용해서 최소성에 해당되는 애들만 combinations에 담아준다.
every를 사용해서 포함하는지 체크해주고 포함하지 않을 때 넣어준다.
const solution = (relation) => {
// 1.
let idxArr = Array.from(Array(relation[0].length), (_, i) => i)
let combinations = [];
// 2.
for(let i=0; i<idxArr.length; i++){
combinations.push(...getCombination(idxArr,i+1))
}
// 3.
combinations = checkUniqueness(relation, combinations)
// 4.
combinations = checkMinimality(combinations)
return combinations.length
}
const getCombination = (arr, selectNum) => {
const results = [];
if(selectNum === 1){
return arr.map(value => [value])
}
arr.forEach((fix, i, origin) => {
const rest = origin.slice(i+1)
const comb = getCombination(rest, selectNum-1)
const attached = comb.map((c) => [fix, ...c])
results.push(...attached)
})
return results
}
const checkUniqueness = (relation, combinations) => {
const results = [];
combinations.forEach((combination) => {
let set = new Set();
relation.forEach((rel) => {
set.add(combination.map(combi => rel[combi]).join(','))
})
if(set.size == relation.length){
results.push(combination)
}
})
return results
}
const checkMinimality = (combinations) => {
const results = [];
while(combinations.length){
results.push(combinations[0])
combinations = combinations.reduce((acc,cur) => {
let notMinimal = combinations[0].every(combination => cur.includes(combination))
if(!notMinimal) acc.push(cur)
return acc
}, [])
}
return results
}
console.log(solution([["a", "1", "aaa", "c", "ng"], ["a", "1", "bbb", "e", "g"], ["c", "1", "aaa", "d", "ng"], ["d", "2", "bbb", "d", "ng"]])) // 5
console.log(solution([["100", "ryan", "music", "2"], ["200", "apeach", "math", "2"], ["300", "tube", "computer", "3"], ["400", "con", "computer", "1"], ["500", "muzi", "music", "3"], ["600", "apeach", "music", "2"]])) // 2
console.log(solution([["100", "100", "ryan", "music", "2"], ["200", "200", "apeach", "math", "2"], ["300", "300", "tube", "computer", "3"], ["400", "400", "con", "computer", "4"], ["500", "500", "muzi", "music", "3"], ["600", "600", "apeach", "music", "2"]])) // 3다른 풀이 2
비트마스크 (조합을 구할 때 재귀보다 비트마스크가 성능이 좋다(수행시간도 빠르고, 코드도 짧고, 메모리 사용량도 적다))
column이 n인 부분집합의 개수는 2^n이다. 공집합을 제외하면 2^n-1이다. 2^n-1만큼 반복해서 부분집합의 경우의 수를 찾아낸다.
for(let i = 1; i < (1 << column); ++i)
2^n-1만큼 반복하는 동안 2차원 배열(relation[j][k])을 순회한다.
배열의 모든 요소를 2진수로 간주하고 1이면 부분집합에 포함되고 0이면 부분집합에 포함되지 않을 것이다. 그러므로 부분집합에 포함될 때만(if((i & (1 << k)) != 0))을 고려해 문자열을 만든뒤, set에 add해준다(keySet.add(key)).
set에는 중복값이 저장되지 않으므로, 중복값이 존재했다면 row와 set.size가 같아질 수 없다. 이 경우 일회성을 만족한다.
duplicateCheck 함수를 통해 최소성을 확인해준다.
논리곱을 사용한다.
function solution(relation) {
let column = relation[0].length;
let row = relation.length;
let count = 0;
let bitMaskList = [];
for(let i = 1; i < (1 << column); ++i) {
let keySet = new Set();
for(let j = 0; j < row; ++j) {
let key = "";
for(let k = 0; k < column; ++k) {
if((i & (1 << k)) != 0) key += relation[j][k];
}
keySet.add(key);
}
if(keySet.size == row && duplcateCheck(bitMaskList, i)) ++count;
}
return count;
}
function duplcateCheck(list, key) {
let size = list.length;
for(let i=0; i<size; ++i) {
if((list[i] & key) == list[i]) return false;
}
list.push(key);
return true;
}다른 풀이 3
비트마스크
[ALGO] 프로그래머스 - 후보키(자바스크립트, javascript)
function solution(relation) {
let answer = 0;
let col = relation[0].length;
let row = relation.length;
let bitmask = [];
for (let i = 1; i < (1 << col); i++) {
let bit = '';
for (let j = 0; j < col; j++) {
if ((i & (1 << j)) !== 0) bit += j;
}
bitmask.push(bit);
bit = '';
}
bitmask.sort((a, b) => a.length - b.length);
while (bitmask.length > 0) {
let col = bitmask.shift().split('').map(Number);
let set = new Set();
relation.map(tuple => {
let tmp = '';
for (let i = 0; i < col.length; i++) {
tmp += tuple[col[i]];
}
set.add(tmp);
});
// 유일성
if (set.size === row) {
answer += 1;
// 최소성
bitmask = bitmask.filter(item => !col.every(v => item.includes(v)));
}
}
return answer;
}시프트 연산자 연습
<< : 지정한 수만큼 비트 전체를 왼쪽으로 이동한다 (left shift)
const leftShift = 4 << 2
console.log(leftShift) // 16 == 4 * 2 * 2
const leftShift2 = 4 << 3
console.log(leftShift2) // 32 == 4 * 2 * 2 * 2
const leftShift3 = 4 << 4
console.log(leftShift3) // 64 == 4 * 2 * 2 * 2 * 2>> : 지정한 수만큼 비트 전체를 오른쪽으로 이동한다 (right shift)
const rightShift = 4 >> 1
console.log(rightShift) // 2 == 4 / 2
const rightShift2 = 4 >> 2
console.log(rightShift2) // 1 == 4 / 2 / 2
const rightShift3 = 4 >> 3
console.log(rightShift3) // 0 == 4 / 2 / 2 / 2AND(&) 연산 : 논리곱 - 두 개 모두 1일 때 1을 반환
console.log(1 & 1) // 1
console.log(1 & 2) // 0
console.log(1 & 3) // 1
...OR(|) 연산 : 논리합
XOR(^) 연산 : 두 비트 값이 같으면 0을 반환, 다르면 1을 반환
NOT(~) 연산 : 1을 0으로, 0을 1로 반환
개념정리 (부분집합)
순열
n개의 원소에서 순서를 고려해 r개의 원소를 선택하는 방법
조합
n개의 원소에서 순서를 고려하지 않고 r개의 원소를 선택하는 방법
부분집합
집합의 원소 일부로 이루어진 집합. 자기 자신, 공집합도 모두 부분집합이다. 조합이 r개를 뽑는 것이라면, 부분집합은 단순히 r개가 아니라 0~n개 모두 뽑는다.
각각의 원소를 선택하는 경우와 선택하지 않는 경우로 나뉘며
전체 시간복잡도는 O(2^n)이 된다.
let arr = [1,2,3,4];
let result = [];
for(let i = 1; i < (1 << arr.length); i++) {
result.push([]);
for(let j = 0; j < arr.length; j++) {
if(i & (1 << j)) result[i-1].push(arr[j])
}
}
console.log(result);
// [[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3],[4],[1, 4],[2, 4],[1, 2, 4],[3, 4],[1, 3, 4],[2, 3, 4],[1, 2, 3, 4]]번외편
모든 경우의 수를 고려해야 한다고 판단되면 완전 탐색 알고리즘을 사용해야 한다.
let numArr = [1, 7]
let set = new Set()
const Rec = (arr,str) => {
if(arr.length) {
for(let i=0; i < arr.length; i++) {
let copy = [...arr]
copy.splice(i, 1)
Rec(copy, str + arr[i])
}
}
if(str > 0) set.add(Number(str))
}
Rec(numArr, '')
console.log(Array.from(set)) // [17, 1, 71, 7]완전 탐색 알고리즘으로는,
조합/순열/부분집합/브루트포스/백트래킹(bfs,dfs) 등을 사용할 수 있다.
비트마스크
이진수로 표현한 뒤, 비트연산자를 사용해서 각각의 변환된 이진수 값을 마스킹하여(가려서) 연산하는 방법.
&(and 연산자)
두 비트가 모두 1이면 1을 반환|(or 연산자)
두 비트 중 하나라도 1이면 1을 반환^(xor 연산자)
두 비트가 서로 다르면 1을 반환<<(left shift 연산자)
예를 들어 1<<3이면 0001을 1000으로 변환한다. 1을 왼쪽으로 이동한다는 의미이다.
예를 들어, 3개 중에서 선택할 수 있는 모든 경우의 수는 1<<3으로 표현할 수 있다.
[1, 0, 0, 0]
3가지로 선택할 수 있는 모든 경우의 수 : 총 8가지
이 8가지 경우의 수는
[1, 0, 0, 0] 보다 작은 2진수 값들이다.
for(let i=0; i<(1<<3); i++) {
console.log(i) // 0 1 2 3 4 5 6 7
}이중에서 2가지만 선택하려면? 1의 개수를 세서 if문으로 판단을 해야 한다.
const color = ['black', 'purple', 'gray']
for(let i=0; i<(1<<3); i++) {
let bin = i.toString(2)
let bitCount = bin.split('1').length-1
bin = bin.padStart(3, '0')
if(bitCount === 2) {
let answer = ''
for(let j=0; j<3; j++) {
if((1<<j) & i) {
answer += color[j] + ' '
}
}
console.log(answer)
/** output
* black purple
* black gray
* purple gray
*/
}
}(let i=0; i<(1<<3); i++)에서 i는 10진수이다.
이 10진수를 2진수로 변환한 뒤, 1의 개수를 세야 한다.
- 10진수를 2진수로 변환하고
let bin = i.toString(2) - 문자열 내 1의 개수 카운트
let bitCount = bin.split('1').length-1
참고로 문자열 내에서 특정 문자 개수를 세려면 split으로 만든 배열의 길이에서 -1을 해줘서 구할 수 있다.
자릿수를 맞춰주기 위해서 padStart() 메서드를 사용했으나 어차피 1의 개수만 카운트하므로 필수는 아니다.
bin = bin.padStart(3, '0')
개수를 구했다면, 그 개수가 2개인 경우를 고려하면 된다. 1의 개수가 2개라는 건, 2개를 선택했다는 의미이다. if(bitCount === 2) {}
이렇게 특정 개수를 선택하지 않고 전체 경우의 수를 찾는다면 부분집합을 구하는 것과 같다. if(bitCount >= 1) {}로 바꾸면 부분집합을 구할 수 있다.
2개일 때, 전체 3개 중에서 조건에 충족하는 요소들을 출력해보면 답이 된다.
참고
