30.md

숫자 짝꿍

시간 초과와 반례 찾기

Try1

function solution(X, Y) {
  const arr = [];
  const x = [...X];
  const y = [...Y];

  x.forEach((s) => {
    const index = y.indexOf(s);
    if (index !== -1) {
      arr.push(s);
      y.splice(index, 1);
    }
  });

  const result = arr.sort((a, b) => +b - +a).join('');
  return result ? (result[0] === '0' ? '0' : result) : '-1';
}

위 코드는 시간초과를 받은 코드이다. 이제까지의 경험으로 보아 forEach 안에서 indexOf는 결국 이중for문이 되고, 이 문제의 X,Y의 길이 조건은 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000 이다. 그래서 어떻게든 forEach 안의 로직을 변경해야할 필요가 있었다.

위 문제에서의 포인트는 몇 개가 중복되었는지를 여부이다. x 문자열을 순회하면서 각 문자가 y에서 있는 여부를 판별하고 y에서 이를 제거해줌으로서 같은 문자열이 있는 개수를 판별할 수 있었다. 하지만 이 과정에서 순회하고 존재여부 판별하는 과정에서 시간복잡도 O(n^2)을 마주하게 된 것이 문제!!

Try2

function solution(X, Y) {
  const arr = [];
  const x = {};
  const y = {};

  Array.from(X).forEach((str) => {
    if (x[str]) x[str]++;
    else x[str] = 1;
  });
  Array.from(Y).forEach((str) => {
    if (y[str]) y[str]++;
    else y[str] = 1;
  });

  for (const [k, v] of Object.entries(x)) {
    if (y[k]) arr.push(k.repeat(Math.min(v, y[k]))); // ✅
  }

  const result = arr.sort((a, b) => +b - +a).join('');

  return result ? (result.indexOf(0) === 0 ? '0' : result) : '-1';
}

두번째 문제 풀이이다. 생각하던 중에 Map(Hash)를 이용하여 각 개수를 맵핑해놓고 이를 이용하는 방식으로 문제를 풀면 어떨까라는 생각을 하게 되었다. 그런데 여기서 문제가 생겼다. 체크박스된 코드에서 말이다. 언듯보면 별 문제가 없어보인다. 왜냐하면 어차피 내림차순을 통해서 정렬할 것이니까 라는 착각때문이다. 이 부분의 반례는 아래와 같다.

arr.push('55');
arr.push('444');

// 이를 내림차순으로 정렬하면 ??
('44455');

// 하지만 실제 가장 큰 수 !!
('55444');

이러한 오류로 인해서 부분문자열로 정렬하는 것이 아니라 문자 하나 단위로 정렬을 하도록 수정하였다.

let str = ''; // ✅ 수정부분
const x = {},
  y = {};

Array.from(X).forEach((s) => {
  if (x[s]) x[s]++;
  else x[s] = 1;
});
Array.from(Y).forEach((s) => {
  if (y[s]) y[s]++;
  else y[s] = 1;
});

for (const [k, v] of Object.entries(x)) {
  if (y[k]) str += k.repeat(Math.min(v, y[k])); // ✅ 수정부분
}

const result = str
  .split('') // ✅ 수정부분
  .sort((a, b) => b - a)
  .join('');

return result ? (result[0] === '0' ? '0' : result) : '-1';

체크박스 부분이 수정된 부분