Node.js)백준 1062번: 가르침

https://www.acmicpc.net/problem/1062

1062번: 가르침

비트마스크로 제대로 풀면 200ms 정도로도 풀 수 있는 듯.. 

 

 

 

const input = require('fs').readFileSync('./dev/stdin').toString().trim().split('\n').map(v=>v.trim())
const [_,K] = input[0].split(' ').map(Number);
const words = input.slice(1);
const base = ['a','n','t','i','c'];

  let answer = 0;    // 정답.
  let leftover = K-5; // 배울 수 있는 알파벳의 수 (a,n,t,i,c는 무조건 배워야함.)
  let candidate = [] // 각 단어별. 단어를 읽는 데 필요한 알파벳  antic 제외. 
  let alpha = []; // 배워야 하는 알파벳 정리. 

  if(leftover<0){ // 5개는 무조건 배워야함^^ 
    answer = 0;
  }else{
    let possible = words.length // 가르칠 수 있는 단어..
    words.forEach(w=>{
      const clear = [...new Set(w.split('').filter(v=>!base.includes(v)))]
      if(clear.length<=leftover){// 배워야 되는 알파벳의 수가  배울 수 있는 알파벳의 수보다 크면 제외
        alpha = [...alpha,...clear];
        candidate.push(clear)
      }else{ // 이런 경우는 지민쌤이 아무리 가르쳐도 못 읽는 거니까 단어 자체를 없앰.
        possible--;
      }
    })

    alpha = [...new Set(alpha)];  // 이게 배워야 할 알파벳.

    if(alpha.length<=leftover){ // 배워야 되는 알파벳이 배울 수 있는 것보다 작거나 같으면 계산할 필요 없음
      answer = possible
    }else{
      // 이제부터 탐색시작. 
    for(let i = 0; i<(1<<alpha.length); i++){
      let sum = 0;
      
      if(countBits(i)==leftover){ // 배울 수 있을 만큼 배웠을 때,
        const learnedAlpha = alpha.filter((_,index)=>i&(1<<index)) // 배운 알파벳.
        candidate.forEach(v=>{    // 각 후보단어를 읽을 수 있는 지 확인. 
          if(canLearn(v,learnedAlpha)){  
            sum++;
          }
        })
      }
      if(sum>answer) answer = sum;
    }
    }

    
  }

  console.log(answer)


function countBits(n){  
  let cnt = 0;
  while(n>0){
     if(n&1){
      cnt++;
     }
     n = n>>1;
   }
   return cnt;
}

function canLearn(word,alpha){
  for(let i = 0; i<word.length; i++){
    const now = word[i];
    if(!(alpha.includes(now))){
      return false
    }
  }
  return true;
}