[프로그래머스 lev2/JS] 가장 큰 수

문제 출처

프로그래머스 lev2 - 가장 큰 수

나의 풀이

1차 시도(런타임 에러/시간초과)

function solution(numbers) {
  let ch = Array.from({length:numbers.length}, () => 0);
  let tmp = [];
  let answer = [];

  function maxNum(L) {
    if (L>=numbers.length) answer.push(tmp.join(''));
    else {
      for (let i=0; i<numbers.length; i++) {
        if (ch[i]===0) {
          ch[i]=1;
          tmp[L]=numbers[i];
          maxNum(L+1);
          ch[i]=0;
        }
      }
    }
  }
  maxNum(0);
  answer.sort();
  return answer[answer.length-1];
}

console.log(solution([6, 10, 2]));

// 혹은 
function solution(numbers) {
  let ch = Array.from({length:numbers.length}, () => 0);
  let tmp = [];
  let answer = '';

  function maxNum(L) {
    if (L>=numbers.length) {
      let str = tmp.join('');
      if (answer < str) answer = str;
    }
    else {
      for (let i=0; i<numbers.length; i++) {
        if (ch[i]===0) {
          ch[i]=1;
          tmp[L]=numbers[i];
          maxNum(L+1);
          ch[i]=0;
        }
      }
    }
  }
  maxNum(0);
  return answer;
}

console.log(solution([6, 10, 2]));

2차 시도(33.3/100)

sort를 변형해야 할 것 같은데 자릿수가 다를 때 어떻게 처리해야 할지가 고민이다

function solution(numbers) {

  numbers.sort((a,b) => {
    a=''+a;
    b=''+b;
    
    let idx=0;
    if (a.length < b.length) {
      while (idx<=b.length) {
        if (a[idx]==undefined) {
          if ('1' < b[idx]) return 1;
          else if ('1' > b[idx]) return -1;  
        }
        if (b[idx]==undefined) {
          if (a[idx] < '1') return 1;
          else if (a[idx] > '1') return -1;  
        }
        else {
          if (a[idx] < b[idx]) return 1;
          else if (a[idx] > b[idx]) return -1;
        }

        idx++;
      }
    } else {
      while (idx<=a.length) {
        if (a[idx]==undefined) {
          if ('1' < b[idx]) return 1;
          else if ('1' > b[idx]) return -1;  
        }
        if (b[idx]==undefined) {
          if (a[idx] < '1') return 1;
          else if (a[idx] > '1') return -1;  
        }
        else {
          if (a[idx] < b[idx]) return 1;
          else if (a[idx] > b[idx]) return -1;
        }

        idx++;
      }
    }
  })
  return numbers.join('');
}

// console.log(solution([6, 10, 2]));
console.log(solution([3, 30, 34, 5, 9]));

다른 풀이 (통과 코드)

내가 풀지 못한 이유는, 문자열을 하나하나의 index로만 접근하려고 했기 때문이다.

예를 들어 34와 3을 비교하면 3과3을 비교하고 4와 undefined를 비교하려고 했다.
근데 아래 풀이처럼 그냥 더해서 계산해버리면, 자릿수 문제를 해결할 수 있다. "3(a)과 30(b)에 대해 303(b+a)이 큰 걸까 330(a+b)이 큰 걸까"

function solution(numbers) {
  numbers = numbers.map(v => `${v}`);
  numbers.sort((a,b) => (b+a) - (a+b));
  return (numbers[0]==='0') ? '0' : numbers.join('');
}

// console.log(solution([6, 10, 2]));
console.log(solution([3, 30, 34, 5, 9]));

문제 조건이 <1_000 임을 응용한 풀이
자릿수가 부족하면 채워놓고 999에서 뺀 값을 index로 사용한다.

function solution(numbers) {
  const buckets = [];

  for (const n of numbers){
      const s = String(n), l = s.length;

      let j = '';
      for (let i = 0; i < 4; i++){
          j += s[l > i ? i : i % l];
      }
      j = 9999 - j;
      buckets[j] = buckets[j] ? buckets[j] + s : s;
  }

  const ans = buckets.join``;

  return ans[0] === '0' ? '0' : ans;
}

// console.log(solution([6, 10, 2]));
console.log(solution([3, 30, 34, 5, 9]));