[Javascript][프로그래머스] 숫자 짝꿍 자바스크립트

프로그래머스

🌷 문제 설명

✏️ 프로그래머스 연습문제: 숫자 짝꿍
두 정수 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

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

😵 첫번째 시도(시간초과)

function solution(X, Y) {
    X = X.split('')
    Y = Y.split('')

    let answer = []
    X.forEach((x)=> {
        if (Y.includes(x)) {
            answer.push(x)
            let idx = Y.indexOf(x)
            Y.splice(idx, 1)
        }
    })
    
    if ( answer.length === 0) {
        return '-1'
    } else if ( answer.join('') == 0) {
        return '0'
    } else {
        return answer.sort((a,b)=>b-a).join('');
    }
}

테스트 케이스 #11~15번이 시간초과로 실패가 났다. 그럼 그렇지. 너가 나에게 쉽게 정답을 줄 리가 없지. 사실 처음에 X, Y split으로 배열로 새로 만들어 줄 때 sorting을 다 해줬는데 혹시 두 번 한 게 시간 걸리는거에 영향을 미치나 싶어서 나중에 한 번으로 바꿨는데.. 별로 큰 차이는 없는 것 같다. 

내 얕은 지식으로는 이놈의 시간복잡도를 줄이는 법을 알아 낼 수가 없어서 질문하기를 뒤져봤는데, 이중포문을 사용하면 시간복잡도가 N^2가 돼서 큰 수가 들어오는 테스트케이스인 #11~#15에서 시간초과가 날 수 밖에 없다는 설명이 있었다. 

---

---

사실 이중 포문이라고 해서 "엥 난 이중포문 없는디?" 싶어서 의아했는데, 누군가의 질문에 댓글을 달아주신 분이 includes, indexOf, splice (ㅋ내 코드에도 다 있음ㅋ) 가 각각 O(n) 시간 복잡도를 따른다고 했다. 

---

---

이 분 덕분에 대충 다른 로직을 생각해 볼 수 있었다. 사실 구글링 하면 쉽게 정답 코드가 나오긴 하지만 사실 그 코드 자체가 썩 이해가 안가서 휘리릭 넘겼는데 이걸 보고 나니 왜 구글에 뜨는 그 분들이 자꾸 숫자를 셌는지 알 수 있었다. 그렇구나 일일히 비교하지 말고 숫자 몇개 나왔는지 카운트만 하면 되는구나.

 

🌷 성공

function solution(X, Y) {
    // 길이 10짜리, 값 0으로 채워진 Array 생성
    const numX = new Array(10).fill(0)
    const numY = new Array(10).fill(0)

    let answer = []
    
    // numX Array에 각 숫자 카운트
    for (let i=0; i< X.length; i++) {
        numX[X[i]]++
    } 
    
    // numY Array에 각 숫자 카운트
    for (let i=0; i< Y.length; i++) {
        numY[Y[i]]++
    }
    
    // numX와 numY 를 10번씩 돌면서 겹치는 부분이 있는지 확인하기
    for (let i=0; i<10; i++) {
        if (numX[i] > 0 && numY[i] > 0) {
        	// 겹치는 숫자 최대 몇 개 까지 쓸 수 있는지 세기
            const count = Math.min(numX[i], numY[i])
            // 사용할 수 있는 숫자 카운트의 최댓값만큼 배열에 넣어주기
            for (let j=0; j < count; j++) {
                answer.push(i)
            }
        }
    }
    
    if ( answer.length === 0) {
        return '-1'
    } else if ( answer.join('') == 0) {
        return '0'
    } else {
        return answer.sort((a,b)=>b-a).join('');
    }
}

 

🌷 코멘트

👉 '00' 과 '0'이 같은지 확인하기 위해 "===" 대신 "==" 사용했음. (다른 사람들은 Number()사용하던데 그게 좀 더 확실한 느낌)
👉 인덱스로 숫자 카운트 하기!
내장함수 쓸 때 얘네들이 어떻게 동작하는지 알고 있으면 좋을 듯.
외면하기만 했던 시간복잡도.. 이제는 마주할 때인가

 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview