[프로그래머스] 기능개발

problem | 가장 큰 수

💭 가장 쉽게 하는 생각

모두 붙여보는 것이다.

• numbers [6, 10, 2]로 만들 수 있는 총 가짓 수는 6개이다.

  numbers의 길이는 1 이상 100,000 이하입니다.

만약, 100,000개를 모두 만들어보는 가짓수는? o(n!)

문제 풀이

1. 입력 받은 numbers를 문자열로 변경한다.

• numbers=[6,10,2] 일 때, 숫자로 내림차순 정렬을 하면 [10,6,2]다. 가장 큰 수는 앞자리가 가장 큰 6이 먼저 와야한다 !

answer=numbers.map((number) => number.toString());

편의상 answer라는 변수 안에 문자열로 변경한 값을 넣어준다.

2. 배열 속 문자열 정렬

answer.sort((a,b)=>b+a-(a+b));

만약 [30,3] 이 있다면, 303보다 330이 더 값이 크기 때문에 [3,30]이 옳은 정렬이다.
a+b = 303
b+a = 330
되기 때문에 [3,30]으로 정렬이 된다.

3. 의미 없는 수 제거
   전체 answer에 0000이라는 값이 들어올 수 있기 때문에

answer.every((a)=> a==="0") 

으로 전체 0인지 확인(만약 전체 0이라면 true를 return 한다.) 해준다.

전체 코드

function solution(numbers) {
  var answer = "";
  answer = numbers.map((number) => number.toString());
  answer.sort((a, b) => b + a - (a + b));
  if (answer.every((a) => a === "0")) {
    return "0";
  }
    
return answer.join("");
}

가장 큰 수 - DFS 문제 풀이

조금 다른 유형의 문제가 들어오면 DFS로 풀이해야 한다.

문제 |
123이 입력된다면 조합 할 수 있는 숫자 중 123보다 큰 수 중 가장 작은 수를 출력해야한다.

function solution(x){
  let num=[];
  let answer=[];

  // 1. x를 배열에 넣고, 정렬
  let temp=x;
  while(temp>0){
    let t=temp%10;
    num.push(t);
    temp=parseInt(temp/10);
  }
  num.sort((a,b)=>a-b);

  // DFS에 필요한 변수 선언

  let tmp=[];
  let len=num.length;
  let ch=new Array(len).fill(0);

  function DFS(L){
    if(L===len){
      let q=parseInt(tmp.join(''))
      if(q>x) answer.push(q);
    }
    else{
      for(let i=0;i<len;i++){
        if(ch[i]===0){
          ch[i]=1;
          tmp.push(num[i]);
          DFS(L+1);
          ch[i]=0;
          tmp.pop();
        }
      }
    }
  }
  DFS(0);
  if(answer.length>0){
    answer.sort((a,b)=>a-b);
    return answer[0];
  }
  else return -1;

}

// console.log(solution(123));
console.log(solution(102368));

그냥, DFS 로 순열을 만들고(n보다 큰 수만) answer에 넣어서 정렬해서 제일 큰 수 중 작은 수를 뽑아내려 했다.