[프로그래머스 Level 1] 숫자 짝꿍

문제:
두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

문제 풀어보기: https://school.programmers.co.kr/learn/courses/30/lessons/131128

 

풀이보기

function solution(X, Y) {
    let arr1 = [...X];
    let arr2 = [...Y];
    let common = arr1.filter((val) => {
        let idx = arr2.indexOf(val);
        if(idx !== -1) {
            arr2.splice(idx, 1);
            return true;
        }
    });
    
    if(common.length === 0) return '-1';
    
    let allZero = true;
    common.forEach((val) => {
        if(val !== '0') allZero = false;
    });
    
    if(allZero) return '0';
    
    return common.sort((a, b) => b - a).join('');
}

 처음에는 배열로 풀었었다.

arr1과 arr2에 각각 X,Y를 배열로 담아주고,

filter 메서드를 사용해서 arr1과 arr2에 공통으로 담겨있는 수를 새로운 배열로 반환해준다.

여기서 공통된 수는 splice를 통해 arr2에서 삭제해줘야한다.

 

그 다음 공통된 수가 없다면 -1을 리턴해주고, 공통된 수가 모두 0이라면 0을 리턴해줘야한다.

두 조건에 다 해당되지 않는다면 common을 내림차순으로 정렬한 뒤 문자열로 반환해주면 끝이다!

 

하지만 이 코드로는 문제를 통과하지 못했다. 왜냐하면 X, Y의 범위가 엄청 크기 때문에 효율적으로 코드를 짜야한다.

function solution(X, Y) {
    let arr1 = [...X];
    let arr2 = [...Y];
    let countMap = {};
    for(let num of arr2) {
        countMap[num] = (countMap[num] || 0) + 1;
    }
    
    let result = [];
    for(let num of arr1) {
        if(countMap[num] > 0) {
            result.push(num);
            countMap[num]--;
        }
    }
    
    if(result.length === 0) return '-1';
    
    let allZero = true;
    result.forEach((val) => {
        if(val !== '0') allZero = false;
    });
    
    if(allZero) return '0';
    
    return result.sort((a, b) => b - a).join('');
}

이럴때 항상 나는 객체를 사용해줬다.

먼저 countMap 객체에 arr2의 수와 카운트를 저장해주고,

arr1을 순회하면서 countMap에 있는 수라면 result에 해당 값을 추가해준 뒤 countMap[num]-- 해준다.

그 이후는 똑같다! 객체를 활용하면 더 효율적으로 문제를 해결할 수 있다.

 

근데 코드가 통과하긴 했지만 그래도 느리긴했다.

배열을 사용했을 때 문제는 indexOf나 splice 등과 같이 배열 이동이 많았기 때문에 더 느렸었는데,

이 문제들을 보완해서 다시 코드를 작성해보았다.

 

function solution(X, Y) {
    const countX = Array(10).fill(0);
    const countY = Array(10).fill(0);

    for (let char of X) countX[char]++;
    for (let char of Y) countY[char]++;

    let result = '';

    for (let i = 9; i >= 0; i--) {
        const commonCount = Math.min(countX[i], countY[i]);
        result += i.toString().repeat(commonCount);
    }

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

    return result;
 }

먼저 countX, countY에 길이가 10인 배열을 0으로 채워준다.

그러는 이유는 숫자가 0 ~ 9까지이기 때문에 미리 채워서 각 인덱스를 숫자라 생각하고 count를 해주기 위해서이다.

그 다음 각각 해당 인덱스에 맞는 수를 count 해준다.

그리고 내림차순 정렬을 위해 9부터 0까지 반복을 하고, 차례대로 공통된 수를 result에 넣어준다.

Math.min을 해주는 이유는 겹치는 수를 방지하기 위해서이다.

 

마지막으로 result를 반환하기 전에 result가 빈 문자열이면 -1을 리턴해주고,

만약 result의 첫 문자가 0이라면 현재 내림차순 정렬이기 때문에 그 문자열은 전부 0이라는 뜻이므로 0을 리턴해주면 끝이다!

 

이렇게 코드를 작성하면 indexOf, map, filter 등의 메서드는 쓰지않아도 되는 제일 효율적인 코드라고 할 수 있다.