[백준 1062번] 가르침 - 자바스크립트(nodejs)

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

1062번: 가르침

const fs = require('fs');
let input = fs.readFileSync('../input.txt').toString().trim().split('\n');
const [N, K] = input.shift().split(' ').map(Number);
const words = ['a', 'n', 't', 'i', 'c'];
input = input.map((v) => v.slice(4, v.length - 4));

const combinations = function* (elements, selectNumber) {
  for (let i = 0; i < elements.length; i++) {
    if (selectNumber === 1) {
      yield [elements[i]];
    } else {
      const fixed = elements[i];
      const rest = elements.slice(i + 1);

      for (const a of combinations(rest, selectNumber - 1)) {
        yield [fixed, ...a];
      }
    }
  }
};

const filterWords = (arr) => {
  return arr.map((v) => {
    const word = [...new Set(v.split(''))].filter((ele) => !words.includes(ele));
    return word;
  });
};

if (K < 5) {
  console.log(0);
} else if (K === 5) {
  const filterWord = filterWords(input);
  console.log(filterWord.filter((v) => v.length === 0).length);
} else {
  const filterWord = filterWords(input);
  const flatWord = [...new Set(filterWord.flat())];

  let answer = 0;

  if (K > [...flatWord, ...words].length) {
    console.log(N);
    return;
  }

  for (let ele of combinations(flatWord, K - 5)) {
    const str = [...words, ...ele];
    let count = 0;
    Loop: for (let i = 0; i < input.length; i++) {
      for (let j = 0; j < input[i].length; j++) {
        if (!str.includes(input[i][j])) {
          continue Loop;
        }
      }
      count++;
    }
    answer = Math.max(answer, count);
  }

  console.log(answer);
}

쉬운 문제이지만 자바스크립트로 풀면 계속 메모리 초과가 난다. 이를 해결할 수 있는 방법은 뭐가 있을까 하다가 

https://kscodebase.tistory.com/520

[node.js] 가르침 ( 백준 1062번 )

이 분의 블로그에 조합 코드를 가져와서 썼더니 바로 통과가 됐다. 코드를 설명하자면

 

Function combinations

조합코드이며, 조합 결과가 obj형태로 반환된다.

Function filterWords

words =  ['a', 'n', 't', 'i', 'c'] 를 제외하고 남는 문자를 리턴해주는 함수이다.

ex) [ 'antihj' ] => ['hj']

 

 

1. 주어진 input에서 중복되는 값인 양끝 4개를 잘라서 배열형태로 리턴해준다.

ex)  [ 'antarctica', 'antahellotica', 'antacartica' ] => [ 'rc', 'hello', 'car' ]

 

2. 기본적으로 K가 5개 이상이어야 만족하는 단어의 개수가 최소 0개라도 되므로 K가 5보다 작으면 그냥 0을 콘솔로 출력해준다.

 

3. K가 5개면 filterWords함수를 이용해 words에 포함되지 않는 않는 문자만 필터링해주고, 길이가 0인 input값의 개수를 콘솔로 출력한다.

=> 길이가 0이라는 건 모두 words안에 포함되어있는 문자이므로 배울 수 있는 문자이다.

ex) [ 'c', 'hello', 'car' ] => [ [], ['h', 'e', 'l', 'o'], ['r']] => 정답: 1개 

 

4. K가 5 초과이면 마찬가지로 filterWords함수를 이용해 문자만 필터링해주고, 해당 문자가 중복되지 않도록 새로운 배열 flatWord에 초기화시켜준다. 

ex) [ 'rc', 'hello', 'car' ]  => [ [ 'r' ], [ 'h', 'e', 'l', 'o' ], [ 'r' ] ]  => [ 'r', 'h', 'e', 'l', 'o' ]

 

5. 만약 flatWord와 words를 합친 길이가 K보다 작다면 모든 언어를 배울 수 있다는 뜻이므로 입력값 N을 콘솔로 찍어준다.

ex) [ 'r', 'h', 'e', 'l', 'o', ...words ].length < K    모든 언어를 배울 수 있음!

 

6. 아니라면 조합 결과를 순회하며 input값에서 만족하는 언어의 개수의 최대값을 구해주고 콘솔로 찍어준다.

 

 

이 문제의 핵심은 K가 5일때 처리를 하냐 마냐에 달린 것 같다. 하지 않으면 문제는 그냥 틀려버린다.

또한 자바스크립트 조합 함수인 아래 함수를 쓰면 메모리 초과로 문제가 풀리지 않는다.

const getCombinations = function (arr, selectNum) {
  const results = [];
  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index) => {
    const rest = arr.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    results.push(...attached);
  });

  return results;
};