[프로그래머스] Lv.1 숫자 짝꿍 (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는 Number가 아닌 String형태로 들어오니까, 각각 X,Y를 배열로 sort()를 돌려서 인덱스별로 비교하고 빼면 되려나..는 중복인 번호가 있으니까 안되고, 그냥 그냥 한가지(y) 배열을 순회하면서 다른 배열(x)의 includes를 사용하고, 있으면 배열에서 지워야겠다
라고 작성한 코드가

function solution(x,y){

  let xArr=[...x].sort();
  let yArr=[...y].sort();
  
  let result="";
  
  yArr.forEach((ele)=>{
    if(xArr.includes(ele)){
      result+=ele
      xArr.shift()
    }
  })

  if(!result.length) return "-1"
  if(+result===0) return "0"
  return [...result].reverse().join("")  
}

짝꿍이 없을때와 짝궁인 번호가 예를들어 "00" 인 경우의 예외처리를 해줬다. 이렇게 하면 기재되어있는 입출력예시 테스트케이스는 다 통과하는데 다른 테스트 케이스에서 통과를 못한다 아마 위의 제한사항에 3000000 이하의 자릿수 때문인 것 같다 (확실하지는 않음)

만약 X,Y의 자릿수가 300만 이라면, 이중 for문만 돌려도 300만번의 제곱만큼 순회 해야 할지도 모른다 위의 내가 작성한 코드처럼 Y의forEach와 그 안의 xArr의 includes 또한 마찬가지인 셈이다.

그래서 보통 다른 글들을 읽어보니 해시 형태의 자료구조를 많이 사용하는 것 같다.

function solution(x,y){
  let obj={}
  let str=""
  let xObj=[...x].forEach((ele)=>{
    obj[ele] ? obj[ele]+=1 : obj[ele]=1 
  })  
  
 console.log(obj)
 { '1': 2, '2': 2, '3': 1 }
 
}

객체를 리터럴로 obj를 만들고 x를 순회하면서 키가 없으면 1로 초기화 하고 있으면 있는값에 1을 더해!
그럼 이제 X의 각 요소가 몇개씩 있는지를 알 수 있다.
다음 Y를 순회하면서 obj의 키값과 비교해 같은게 있으면 갯수를 내려주자

function solution(x,y){
  let obj={}
  let str=""
  let xObj=[...x].forEach((ele)=>{
    obj[ele] ? obj[ele]+=1 : obj[ele]=1 
  })  
  
  for(let num of y){
    if(obj[num]){
      obj[num]-=1
      str+=num
      if(obj[num]===0) delete obj[num]
      // 1
      continue
    }
    }
    
 }

같은 값이 있으면! -1을 해주고 str에 넣어준다. 중복되는 숫자 때문에 값이 0이 되면 객체에서 해당 프로퍼티를 삭제!
continue는 글을 작성하면서 생각한건데, 만약 300만개가 들어온다 가정할 때 if문의 조건이 충족되지 않으면 다음 num으로 넘어가니까
시간을 더 단축시킬 수 있지 않을까? 해서 넣어봤는데 이 부분은 따로 한번 서칭을 해봐야 할 것 같다.

✅ 내가 작성한 답안

function solution(x,y){
  let obj={}
  let str=""
  let xObj=[...x].forEach((ele)=>{
    obj[ele] ? obj[ele]+=1 : obj[ele]=1 
  })  
  
  for(let num of y){
    if(obj[num]){
      obj[num]-=1
      str+=num
      if(obj[num]===0) delete obj[num]
      continue
    }
    }
  
    if(str==="") return "-1"
    if(+str===0) return "0"
    let result=[...str].sort((a,b)=>b-a)
    return result.join('')
}

짝궁이 없을때와, "00"인경우를 예외처리하고 가장 큰수를 스트링 형태로 return 했다.

출처 https://school.programmers.co.kr/learn/courses/30/lessons/131128