[프로그래머스] 숫자 짝궁

문제 설명

두 정수 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	RESULT
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

설명
1.
X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.

2.
X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.

3.
X, Y의 짝꿍은 10이므로, "10"을 return합니다.

4.
X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.

5. 
지문에 설명된 예시와 같습니다.

 

 

문제 풀이

---

1.  x, y의 숫자를 하나씩 비교하여 추출한뒤 그중에서 가장 큰 정수 만들기

    let yArr = Y.split("");
    let xArr = X.split("");
    let newArr=[];
    for(let i = 0; i<xArr.length; i++){
        for(let j = 0; j < yArr.length; j++){
            if(xArr[i]===yArr[j]){
                newArr.push(xArr[i])
                yArr.splice(yArr.indexOf(xArr[i]),1)
            }
        }
    }

 

2. 짝궁이 존재하지 않으면 결과는 -1

    if(newArr.length===0){
        return "-1"
    }

 

3. 궁을 구했을때 0으로만 되어있다면 짝궁은 0

    let zeroCount = 0
    for(let i =0; i<newArr.length; i++){
        if(newArr[i] === '0' ){
            zeroCount++
        }
    }
    if(zeroCount === newArr.length){
        return "0"
    }

 

4. 만약 같은 숫자가 x에는 3개, y에는 2개 있다면 짝궁은 2개가 되는것.

  newArr.sort((a,b)=>b-a).join("")

 

 

결과

---

테스트는 통과를 하였지만 테스트 케이스에서는 실패와 시간초과가 나왔다.

 

문제 찾기

1. (자릿수) ≤ 3,000,000

     → 길이 7을 1씩 증가하면서 다 찾게 된다.즉, X와 Y모두 3백만일때 7^2를 돌아가면서 비교를 해야하는 것이다.

 

2. 로직상의 문제로 인해 비교되지 않는 부분이 생기는것 같다.

 

해결해보기

전부 다 돌지 말고 한번의 로직을 활용하여 두 수를 비교하고 배열에 추가 하는 식으로 해야한다.

    for(let i = 0; i < 10; i++) {
        let x_cnt = X.filter(x => Number(x) === i).length; 
        let y_cnt = Y.filter(y => Number(y) === i).length; 
        answer += i.toString().repeat(Math.min(x_cnt, y_cnt)); 
    }

• 최대 3백만을표현하는 수의 각 자릿수는 0 이상이면서 9이하이다.

• 각 자리를 문자열로 만들어둔뒤 filter로 하나씩 꺼내오면서 숫자로 만들어준다.

• 현재 수와 filter로 걸러낸 현재 자리수의 갯수(길이)를 반환한다.

• 현재 반환한수를 비교해서 가장 작은수가 같은 수임으로 그 수만큼 새로운 배열에 문자열로 바꿔서 추가해준다.

  ex ) i = 1, x_cnt = 3, y_cnt = 4라면 1이 3개 4개 있다는 뜻이므로 동일한 같은 수는 1이 3개 있다는 것이다.

 

    // 짝궁이 존재하지 않으면 결과는 -1
    if(answer===''){
        return "-1"
    }
    
    // 짝궁을 구했을때 0으로만 되어있다면 짝궁은 0
    else if(answer.split('').filter(x => x === "0").length === answer.length) { // 전부 0 밖에 없다면 0
        return "0";
    }
    
    // 만약 같은 숫자가 x에는 3개, y에는 2개 있다면 짝궁은 2개가 되는것.
    else {
        return answer.split('').sort().reverse().join(''); // 내림차순 정렬해서 return
    }

 

최종 코드

function solution(X, Y) {
    // x, y의 숫자를 하나씩 비교하여 추출한뒤 그중에서 가장 큰 정수 만들기
     Y = Y.split("");
     X = X.split("");
    let answer="";
    for(let i = 0; i < 10; i++) {
        let x_cnt = X.filter(x => Number(x) === i).length; 
        let y_cnt = Y.filter(y => Number(y) === i).length; 
        answer += i.toString().repeat(Math.min(x_cnt, y_cnt)); 
    }   
    
    // 짝궁이 존재하지 않으면 결과는 -1
    if(answer===''){
        return "-1"
    }
    
    // 짝궁을 구했을때 0으로만 되어있다면 짝궁은 0
    else if(answer.split('').filter(x => x === "0").length === answer.length) { // 전부 0 밖에 없다면 0
        return "0";
    }
    
    // 만약 같은 숫자가 x에는 3개, y에는 2개 있다면 짝궁은 2개가 되는것.
    else {
        return answer.split('').sort().reverse().join(''); // 내림차순 정렬해서 return
    }
}