[Algorithm] 숫자 짝꿍

📋 문제 설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

입출력 예

"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

✏️ 풀이

문자열의 각 숫자를 카운팅해서 큰 수부터 중복되는만큼 answer에 더해주면 된다고 생각했다.

 

get, set 작업이 많이 일어날 때에는 객체보다 Map이 효율적이기 때문에 Map을 사용해서 각 숫자를 카운팅했다. 또한 큰 수부터 answer에 반복해서 더해줘야 하기 때문에 하나의 hash(Map)를 정렬해주고 만약 다른 hash에 없다면 continue 시켜줬다. 이때 String의 메서드인 repeat을 사용해서 answer에 가능한만큼 더해줬다.

 

대부분 통과했지만 일부 테스트 케이스에서 시간초과가 발생해서 어느 부분이 문제인지 생각해보았다. 결국 찾은 부분이 answer를 반환하는 부분이었다."00"처럼 "0"이 중복되는 경우 중복되는 "0"을 제거해줘야 하는데 이때 BigInt를 사용했다. 문제는 형변환이었다. 형변환을 해서 숫자로 변환하고 문자열로 다시 변환을 해주었는데 이 작업이 생각보다 오래 걸리는 작업이었던 것 같다. 따라서 "00"처럼 "0"이 중복될 수 있는 경우 answer 문자열의 첫자리가 "0"일 때 큰 값부터 진행을 했기 때문에 절대 "0123"과 같은 경우가 나올 수 없으므로 "0"을 반환해주고 만약 answer이 빈문자열인 경우 "-1"을 반환함으로서 문제를 해결했다.

 

⌨️ 코드

function solution(X, Y) {
  var answer = '';

  const hash1 = new Map();
  const hash2 = new Map();

  for (const n of X) hash1.set(n, (hash1.get(n) || 0) + 1);
  for (const n of Y) hash2.set(n, (hash2.get(n) || 0) + 1);

  const sortedHash1arr = [...hash1.entries()].sort((a, b) => b[0] - a[0]);
  for (const [k, v] of sortedHash1arr) {
    if (!hash2.get(k)) continue;
    answer += k.repeat(Math.min(v, hash2.get(k)));
  }

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