[프로그래머스] 가장 큰 수 (Lv. 2 JavaScript)

📝 문제 설명

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

프로그래머스

목표: 배열로 주어진 정수들을 이어 붙여서 만들 수 있는 가장 큰 수 조합을 알아내는 것이 목표

핵심조건:

• numbers 배열의 길이는 1 이상 100,000 이하
• numbers의 원소 즉, 주어지는 정수의 크기는 0 이상 1000 이하
• 문자열로 return 해줘야 한다.

---

🔍 풀이 과정 (나만의 풀이 전략)

주어진 정수 배열 numbers 의 요소들을 재배치하여 만들 수 있는 가장 큰 수를 반환하는 문제로, 예를 들어 [6, 10, 2]로 주어진 경우 만들 수 있는 조합은 6102, 6210, 2106… 등등이 있다 여기서 만들 수 있는 가장 큰 수는 6210 일 것이다.

이를 위해서 JS의 정렬 메서드 sort()를 사용한다. 이 때 정렬할 두 요소를 앞뒤로 이어붙인 값 중에 더 큰 경우를 조건으로 정렬을 한다.

예를 들어 [6, 10, 2]의 케이스의 경우

• “610”과 “106” 중 더 큰 값은 610이므로 6을 앞에 배치하고
• 다음 “102”와 “210”중에서는 210이 더 크므로 2를 앞에 배치

이러한 방식으로 정렬하면 가장 큰 수 조합의 정답인 “6210”을 구할 수 있다.

이 때 주의 해야 할 예외 케이스는 주어진 numbers 배열이 [0, 0, 0]과 같이 0으로만 구성된 경우에는 정답이 000으로 나오게 되므로 이 예외 케이스를 고려해서 최종 반환할 때 answer를 숫자로 변환했을 때 값이 0이라면 “0”으로 반환하도록 처리한다.

🛠️ 트러블슈팅

처음에는 주어진 숫자 요소에서 앞자리 자릿수의 크기에 따라 정렬하는 방식으로 접근하려고 했다. 맨 앞자리 수가 큰 숫자를 앞에 배치하는 식으로 구현했는데, 이 경우 문제점은 앞자릿수가 동일한 경우였다.

예를 들어 [8, 82, 819]의 경우 모두 맨 앞자리의 수는 8로 같은데 이 경우에는 어떤 기준으로 이 세 숫자를 정렬해야할까? 고민해봤고 “만약에 앞자리가 동일하면 그 다음 자릿수를 비교하는 식으로 해보자” 생각했으나,

이 경우 문제점이 8과 82를 비교할때 앞자리 수가 같으므로 다음 자리수를 비교하면 8은 undefined이고 82는 2인데 undefined와 2를 비교할 수는 없기 때문이다. 이러한 예외 케이스까지 처리하려면 매우 복잡해졌고 코드의 직관성도 떨어진다.

거기에다 이 방식으로 정렬하는 경우 성능 면에서도 좋지 않은데, 핵심 조건에 의하면 numbers의 크기는 최대 100,000 (N=100,000) 배열 내부 원소의 크기는 최대 1,000 (D=4)이다.

그렇다면 최대 숫자가 네자리까지 있다는 것인데 모든 numbers의 요소들을 정렬할 때마다 최대 4번의 자릿수를 매번 비교 연산하면 시간 복잡도는 O(D * N log N) 이 된다.

---

💻 코드 (Code)

function solution(numbers) {
    var answer = '';
    const strNumbers = numbers.map((num) => num.toString()).sort((a, b) => {
        return (b+a) - (a+b)
    });

    strNumbers.forEach((num) => {
        answer += num;
    })

    return Number(answer) !== 0 ? answer : "0";
}

최적화된 코드

function solution(numbers) {
    var answer = '';
    const strNumbers = numbers.map((num) => num.toString()).sort((a, b) => {
        return (b+a) - (a+b)
    });

    answer = strNumbers.join("")

    return Number(answer) !== 0 ? answer : "0";
}

forEach를 활용해 문자열을 순회하며 누적하는 방식 대신 join() 고차 함수를 사용하는 방법이 있다.

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

sort()

sort() 함수에 대해 복습 내용 정리

• sort() 함수의 기본 정렬 기준은 ‘유니코드(문자열)’ 기준으로 정렬을 한다.
• const numbers = [1, 2, 10, 20]; numbers.sort(); console.log(numbers); // Expected: [1, 2, 10, 20] -> Actual: [1, 10, 2, 20]
• sort() 함수 내부에 콜백함수를 정의하여 정렬 기준을 커스텀할 수 있다. 콜백함수는 sort((a, b) ⇒ return b- a) 와 같이 비교하는 함수를 정의 해야한다.
• 자바스크립트에서(V8 엔진) sort() 함수는 Timsort 방식을 사용한다.
  • 이 때 Timsort 알고리즘이란 MergeSort와 Insertion Sort의 장점을 결합한 하이브리드 정렬 알고리즘으로 퀵 정렬의 단점인 최악의 경우 O(N^2) 까지 성능이 떨어지는 경우를 보완하는데
  • MergeSort 방식을 기반으로 하기 때문에 최악에 상황에서도 O(N logN) 보장한다.
  • 또한 동일한 값의 상대적인 순서가 유지되는 Stable Sort 특징을 가진다.

참고자료: Tim sort에 대해 알아보자 https://d2.naver.com/helloworld/0315536

 

join()

join() 메서드는 배열의 모든 요소를 연결해 하나의 문자열로 만들어 준다.

• join(): 인자를 생략하면 기본값으로 쉼표(,)를 사용해 연결한다.
• join(’’): 빈 문자열을 인자로 넘겨주면 요소 사이에 아무것도 넣지 않고 연결한다.
• join(’-’): 지정한 구분자를 요소 사이에 삽입한다.

그렇다면 이 문제에서 forEach 사용보다 join()이 더 최적화된 코드라고 볼 수 있을까? 이는 forEach의 콜백 함수 내부에서 answer += num 연산으로 문자를 더해주고 있는데, 이 방식은 자바스크립트의 특성 상 문자열은 불변(Immutable) 객체이다. 즉, += 연산을 할 때 마다 기존 문자열이 수정되는 것이 아니라 메모리 상에 새로운 문자열 객체가 생성되고 버려지는 과정을 반복한다. 만약 배열의 크기가 N=100,000 이라면 총 100,000번의 위 과정을 반복하는 오버헤드가 발생하게 된다.

반면에 join(’’) 의 경우 자바스크립트 내부 엔진에서 배열의 길이를 미리 계산한 후 한 번의 메모리 할당으로 문자열을 결합하기 때문에 성능면에서 이러한 경우 더 최적화된다고 볼 수 있다.

---

💬 마무리하며

이번 문제를 해결하면서 아쉬움이 많이 남았습니다. ‘두 요소를 앞 뒤로 이어 붙여서 크기를 비교하여 정렬한다’ 라는 접근을 결국 스스로 해내지 못하고 힌트를 얻고 해결한 점이 많이 아쉬웠습니다. 스스로 한없이 부족하다는 점을 계속해서 느끼고 있습니다.

하지만 그렇다고 포기하지 말고 꾸준히 나아가는게 중요하다 생각하고 이번에는 매일 꾸준히 알고리즘 문제 풀이에 정진해야겠습니다. 모두 파이팅!