JS Practice) 프로그래머스 Lv.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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

입출력 예

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

 

첫번째 접근

:  X, Y를 split 해서 문자로 이뤄진 배열을 만든 후, X 배열을 순회하며 각 요소가 Y 배열에 있는지 확인했다. 만약 있으면 Y의 해당 인덱스의 요소를 false로 바꾸어주었고 X의 해당 요소를 숫자로 변환하여 nums배열에 추가해주었다. 이후 nums 배열의 요소를 내림차순으로 정렬한 후 문자열로 만들어 str에 할당해주었다. str의 길이가 0 보다 큰 경우 str을 숫자로 형변환 한 후 문자로 다시 형변환하여  '00'과 같은 경우를 처리해주었다. 그러나 테스트 케이스는 통과했지만, 최종 통과는 되지 않았다. (시간초과 & 실패)

function solution(X, Y) {
    X = X.split('')
    Y = Y.split('')
    let nums = []
    
    X.forEach(num => {
        if(Y.includes(num)) {
            let idx = Y.indexOf(num)
            Y[idx] = false
            nums.push(Number(num))
        }
    })
    
    let str = nums.sort((a, b) => b-a).join('')

    return str.length > 0 ? Number(str).toString() : '-1'
}

 

 

두번째 접근

: X와 Y의 길이가 너무 길어서 그럴까? Set()을 사용해 중복되지 않은 요소로만 구성된 X 배열 arr을 만든 후, 이를 순회하며  Y 배열에 해당 요소가 있으면 배열 X와 Y 각각에서 해당 요소로 이뤄진 배열을 생성했다. 그리고 둘 중 짧은 길이를 가진 배열(중복되는 요소의 수)을 nums에 넣어주었다. 하지만 여전히 최종 통과가 되지 않았다. 

function solution(X, Y) {
    X = X.split('')
    Y = Y.split('')
    let nums = []
    let arr = new Set(X)
    
    arr.forEach(num => {
        if(Y.includes(num)) {
            let x = X.filter(el => el === num)
            let y = Y.filter(el => el === num)
           x.length > y.length ? nums.push(...y) : nums.push(...x)
        }
    })
    
        let str = nums.sort((a, b) => b-a).join('')

    return str.length > 0 ? Number(str).toString() : '-1'
}

 

 

세 번째 접근

Number()와 parseInt()를 사용하니, 시간초과가 발생한다. 위 문제 처럼 매우 큰 숫자는 Number()를 사용하면 성능이 저하될 수 있다고 하여 parseInt()를 사용해 형변환을 시도했지만, 이 또한 역시 시간초과를 야기했다. 

X와 Y를 split() 한 후, 이를 내림차순으로 정렬했다. 만약, 이 새로운 X와 Y를 문자열로 만들었을때 동일하면 해당 문자열을 반환했다. 

다음으로 배열 arrX, arrY을 선언해 X, Y의 고유한 값으로만 구성된 배열을 만들어 주었다. 이후 배열  arrX를 돌며 각 요소(num)가 arrY 에 포함되어져 있으면, 배열 X, Y에 있는 해당 요소로 이뤄진 문자열을 변수  x, y에 할당했다. 이후 nums 변수에 x, y 중 짧은 요소를 더해주었다. 추가로 X, Y 배열에서 num을 제거해주었다.

function solution(X, Y) {
    X = X.split('').sort((a, b) => b-a)
    Y = Y.split('').sort((a, b) => b-a)
    
    if(X.join('') === Y.join('')) return X.join('')
    
    let nums = ''
    let arrX = [...new Set(X)]
    let arrY = [...new Set(Y)]
    
    arrX.forEach(num => {
        if(arrY.includes(num)){
            let x = X.filter(el => el === num).join('')
            let y = Y.filter(el => el === num).join('')
            
            X = X.filter(el => el !== num)
            Y = Y.filter(el => el !== num)
            
            nums += x.length > y.length ? y : x
        }
    })
    
    if(nums.length === 0) return '-1'
    if(nums.split('').every(el => el === '0')) return '0'
    return nums
}

 

 

solution

function solution(X, Y) { // "100", "2345"
    let result = '';
    const numObj = {}; 

    for (const char of X) {
        numObj[char] = (numObj[char] || 0) + 1;
    }
    
    console.log(numObj) // 	{ '0': 2, '1': 1 }

    for (const char of Y) {
        if (!numObj[char]) continue;
        result += char;
        numObj[char]--;
    }
    
    console.log([result, numObj]) // ["", {"0":2,"1":1}]

    if (result === '') return '-1';
    if (+result === 0) return '0';
    return [...result]
        .map((num) => +num)
        .sort((a, b) => b - a)
        .join('');    
}