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

https://school.programmers.co.kr/learn/courses/30/lessons/42746

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

numbers - 0 또는 양의 정수가 담긴 배열

 

출력

return - numbers 배열로 만들 수 있는 가장 큰 정수 (문자열로 반환한다.)

제한사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

풀이

막상 정답을 알면 허무한 코드이다. 단계별로 나누려고 했으나 너무 복잡하고 어려워서 그만 두었다.

문제 그대로 정렬할 때에 버블 정렬을 이용해서 정렬한다.

 

가령 a 정수와 b 정수가 주어졌다고 하자. ab와 ba 중에 큰 수로 정렬한다. a가 90이고 b가 9라면 909와 990이니 b가 앞으로 정렬되는 것이다. 따라서 말 그대로 코드도 이와 같이 짰다.

 

시간 복잡도는 정렬할 때 걸리는 시간 복잡도를 기준으로 O(nlogn)이다.

공간 복잡도는 배열을 저장하는 것이 가장 큰 경우이므로 O(n)이다.

코드

function solution(numbers) {
  numbers.sort((a, b) =>
    "" + a + b > "" + b + a ? -1 : 1
  );
  return numbers[0] == 0 ? "0" : numbers.join("");
}

 

두 번째 보는 것인데도 쉽지 않았다.

이거 말고는 좀 더 깔끔한 설명이 나오지 않을 거 같다.

이런 경우는 외워서 흡수하자.