[프로그래머스] 가장 큰 수 (JavaScript)
알고리즘 문제풀이 [프로그래머스] 가장 큰 수 (JavaScript)
프로그래머스 Level 2 - 가장 큰 수
- 문제 분류:
정렬 - 문제 출처: 프로그래머스 Level 2 - 가장 큰 수
- 라벨:
Level 2,JavaScript
문제
- 0 또는 양의 정수로 이루어진
numbers배열에서 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제 - 입력: 0 또는 양의 정수로 이루어진 배열
- 출력: 이어붙여 만들 수 있는 가장 큰 수를 알아내 문자열로 리턴
풀이1
- numbers 배열의 각 숫자들을 문자열로 변환한다.
numbers.map((num) => num + '')
- 문자열로 변환된 숫자들을 조합하며 비교해 정렬한다. (‘6’, ‘10’ => ‘106’-‘610’ => ‘610’이 더 크기 때문에 ‘6’이 배열의 앞쪽으로 갈 것이다.)
sort((a, b) => b + a - (a + b))
- 정렬이 완료된 후 배열의 요소들을 잇는다.
join('') - 문자열이
0으로만 구성되어있을 경우0을 리턴한다.("0000"일 수도 있기 때문)return answer[0] === '0' ? '0' : answer;
🏷️ Syntax
sort():sort()에는 매개변수로 함수가 들어갈 수 있다. 이 함수의 반환 값에 따라 비교되는 두 요소인 a, b의 순서가 정해진다.
- 음수: a, b(a를 b보다 낮은 인덱스로 정렬한다. = a가 먼저 온다.)
- 0: 그대로(a, b의 자리를 바꾸지 않음)
- 양수: b, a
- 빈 배열에 map을 돌리면 당연히 돌지 않고 빈배열이 반환된다.
- push() 할 때 인자가 생략되면 아무 것도 추가되지 않는다.(당연)
풀이1 코드
function solution(numbers) {
let answer = "";
answer = numbers
.map((num) => num + "")
.sort((a, b) => b + a - (a + b))
.join("");
return answer[0] === "0" ? "0" : answer;
}
-
시간 복잡도: O(n log n)
map은 n번 돈다. O(n)sort()에서 비교할 때 비교하는 횟수가 n, n-1, n-2, … 이렇게 작아질 것 같다. 일단 Chrome에서sort()의 시간 복잡도는 O(n log n) 이다.- O(n) + O(n log n) + … 의 경우 시간 복잡도가 가장 큰 것을 선택하면 된다.
시간 복잡도 계산시,
.(dot)문법으로 이어진 것은 중첩이 아니다.
풀이2 (통과X)
- 순열을 이용해 모든 경우의 수를 구한 뒤 이중에서 최대값을 구했다.
- 테스트 케이스 2가지는 통과하나 제출시
signal: aborted (core dumped)나런타임 에러가 발생한다. 리턴조건이 잘못 작성되어 재귀 호출이 너무 깊어져 에러가 나는건가 싶은데 정확히 모르겠다.
풀이2 코드
function getPermutations(arr) {
const selectNumber = arr.length;
arr = arr.map((n) => n + ""); // arr의 모든 요소를 문자열로 변환
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; // 해당하는 fixed를 제외한 나머지 배열
const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
}
function solution(numbers) {
let answer = 0;
let results = [];
results = getPermutations(numbers).map((v) => Number(v.join("")));
answer = Math.max(...results) + "";
return answer;
}
const numbers = [3, 30, 34, 5, 9];
const result = solution(numbers);
