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

문제 설명

 

두 정수 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개 5개 나타나므로 남는 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

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

 

 

 

나의 풀이

 

문제를 보고 매우 간단하게 풀 수 있겠다고 생각했다.

두 개의 정수 X, Y를 배열의 형태로 만든 뒤에 includes()를 사용해서 서로 겹치는 element를 새로운 배열로 뽑아낸 다음 배열을 내림차순 정렬해서 요소 하나씩 더해주면 되겠다고 생각했다.

(내림차순으로 해야 가장 큰 수가 나올 것이고, 문자열이기 때문에 더하면 앞에서부터 나열할 수 있기 때문에)

 

 

 

First Code

 

function solution(X,Y) {
    const arrX = X.split("");
    const arrY = Y.split("");
    const commonElementArr = [];
    
    arrY.forEach((el)=>{
        if(arrX.includes(el)){
            return commonElementArr.push(el)
        }
    })

    commonElementArr.sort((a,b)=> Number(b)-Number(a))

    let result= "";
    if(commonElementArr.length && !commonElementArr.every((el)=>el==="0")){
        commonElementArr.forEach((el)=>result += el)
    } else if(commonElementArr.length && commonElementArr.every((el)=>el==="0")){
        result = "0"
    } else {
        result = "-1";
    }
    console.log(result)
    return result;
};

 

첫 구상한 것에 살짝 덧붙여서, 문제의 요건에 맞게 배열의 요소가 모두 0인 경우 0을 리턴하게 해주었고 배열의 요소가 한 개도 없을 경우 -1을 리턴하게 만들어 주었다.

 

정답을 확인해보니 (9개/17개)를 맞추며 정답률 50퍼센트가 간신히 넘었다.

 

 

 

Second Code

 

다시 한 번 생각해보니 내가 위에 짠 코드는 X배열의 길이가 Y배열의 길이보다 긴 경우에만 성립하는 코드였다. 따라서 arrX와 arrY를 비교해서 배열의 길이가 더 작은 배열이 반복문을 돌도록 다시 작성해주었다.

 

function solution(X,Y) {
    const arrX = X.split("");
    const arrY = Y.split("");

    const commonElementArr = [];
    if(arrX.length>arrY.length){
        arrY.forEach((el)=>{
            if(arrX.includes(el)){
                return commonElementArr.push(el)
            }
        })
    } else {
        arrX.forEach((el)=>{
            if(arrY.includes(el)){
                return commonElementArr.push(el)
            }
        })
    }
    commonElementArr.sort((a,b)=> Number(b)-Number(a))

    let result= "";
    if(commonElementArr.length && !commonElementArr.every((el)=>el==="0")){
        commonElementArr.forEach((el)=>result += el)
    } else if(commonElementArr.length && commonElementArr.every((el)=>el==="0")){
        return "0"
    } else {
        result = "-1";
    }
    return result;
};

 

하지만 역시나 오답이 뜬다. 아직도 간과한 것이 있었다. 배열 요소끼리의 중복을 생각해주지 못했던 것이다.

 

 

 

Third Code

 

예를 들면 arrX =[1,2,0,0,0] , arrY = [1,0] 이라고 했을 때 , 정확한 조건 하에서는 둘의 중복값인 1과 0만 뽑혀야 한다.

하지만 내 코드에서는 arrX의 반복문을 돌며 arrY.includes(el)을 하기 때문에 arrX에 있는 3개의 0이 모두 포함된 결과값이 나온다는 것이었다. 

(왜냐하면 X의 요소가 0 일때, Y배열에는 언제나 0이 존재하기 때문에 0이 리턴된다)

따라서, 한 개의 X의 요소는 한 개의 Y의 요소에만 대응하도록 만들어주어야 했다. 그렇게 해서 생각한 바가 '각각의 요소가 대응했을 때 그 대응된 Y배열의 요소는 지워주자'라는 것이었다. 그 후 splice()메서드를 이용해 대응되는 Y배열의 요소를 제거해줬다.

 

function solution(X,Y) {
    const arrX = X.split("");
    const arrY = Y.split("");

    const commonElementArr = [];
    if(arrX.length>arrY.length){
        arrY.forEach((el)=>{
            if(arrX.includes(el)){
                arrX.splice(arrX.indexOf(el),1)
                return commonElementArr.push(el)
            }
        })
    } else {
        arrX.forEach((el)=>{
            if(arrY.includes(el)){
                arrY.splice(arrY.indexOf(el),1)

                return commonElementArr.push(el)
            }
        })
    }

    commonElementArr.sort((a,b)=> Number(b)-Number(a))

    let result= "";
    if(commonElementArr.length && !commonElementArr.every((el)=>el==="0")){
        commonElementArr.forEach((el)=>result += el)
    } else if(commonElementArr.length && commonElementArr.every((el)=>el==="0")){
        result = "0"
    } else {
        result = "-1";
    }

    return result;
};

 

첫 코드도 지저분하다고 생각했는데, 코드가 점점 지저분해진다..

그래도 일단 실패하는 문제는 없다. 다만..... 또....시간초과.......!!!!!!

17개의 테스트 코드 중 5개가 시간 초과가 떴다.. 하긴 X와 Y의 길이가 최대 300만이니까 반복문을 많이 쓰게 되면 당연히 시간초과 뜰 수 밖에,,,

 

이제 실패하는 문제는 없기 때문에 코드를 조금 더 간결하게 짜보기로 했다.

 

 

 

Forth Code (진행 중)

 

아무리 생각해도 시간을 줄일만한 특별한 수가 떠오르지 않는다.

처음 문제를 봤을 때 생각했던 부분이 'X,Y문자열 그대로 가져와서 사용하기'와 'filter 메서드 이용해서 풀기'였다.

이렇게 생각한 이유는 문자열 그대로 들고와서 사용하면 배열을 만들고 정리하는 시간이 줄어들지 않을까 라는 생각에서 해보게 되었고 filter메서드를 쓰게된 이유는 코드가 조금 더 간결해지지 않을까 하는 이유에서 사용하게 되었다.

 

우선 두 코드 모두 완벽하게 만드는 데 실패했고 실패한 이유를 적어보겠다.

문자열을 그대로 들고와서 사용하는 문제는 배열을 따로 만들지 않고 어느정도 부분까지는 만들 수 있었지만 부득이하게 배열메서드를 사용해야 하는 부분에서는 사용할 수 없어 막히게 되었다. 

 

filter메서드로 푼 코드는 다음과 같다.

 

function solution(X,Y) {
    const arrX = X.split("");
    const arrY = Y.split("");

    let resultArr = [];
    if(arrX.length>=arrY.length){
        const commonElementArr = arrY.filter((el)=>{
            return arrX.includes(el)
        })
        resultArr = [...commonElementArr]
    } else {
        const commonElementArr = arrX.filter((el)=>{
            return arrY.includes(el)
        })
        resultArr = [...commonElementArr]
    }

    resultArr.sort((a,b)=> Number(b)-Number(a))
    console.log(resultArr)
    let total = "";
    if(resultArr.length===0){
        total = "-1";
    } else if(resultArr.every((el)=>el==="0")){
        total = "0";
    } else {
        resultArr.forEach((el)=> total+= el)
    }
    console.log(total)
    return total;
}

 

filter메서드로 짠 코드는 모든 경우를 모두 수용할 수 있지만 단 한 가지 조건을 수용하지 못한다. 그것은 바로 Second Code에서 못했던 'X배열과 Y배열의 중복'에 관한 문제였다. 물론 Third Code에서는 splice()메서드를 사용해서 문제를 해결했지만 위 같은 경우는 작업하고 있는 배열을 상대로 splice를 쓰게 되면 순서가 무너질 수 있어 사용할 수 없었다. 결국 중복해결을 하지 못한 코드가 완성되었다..

 

시간초과를 해결하던, filter로 만들어보던 제대로 한번 만들어봐야겠다..... 요새 진짜 맨날 시간초과 떠 ㅡㅡ