[프로그래머스] 가장 큰 수 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 1개 케이스 실패)

function solution(numbers) {
    return numbers.map(v => v.toString()).sort((p, c) => p + c > c + p ? -1 : 1).join("")
}

 

11번 케이스에서 실패가 나왔습니다. 원인을 찾지 못하다가 케이스 중 0으로 이루어진 numbers에서 "000..."으로 나와 문제가 발생하더군요. 기댓값이 "0"인걸로 보입니다. 문제의 제한 사항에 0이 있었는데도 못보고 계속 다른 케이스만 생각하다가 시간을 많이 썼네요.

 

작성 코드 (2차 시도 / 통과)

function solution(numbers) {
    if (!numbers.reduce((acc, curr) => acc + curr, 0)) return "0" // 합이 0인 경우
    return numbers.map(v => v.toString()).sort((p, c) => p + c > c + p ? -1 : 1).join("")
}

해당 경우만 조건을 넣어주고 처리하면 됩니다. 

 

구현 로직

이 문제는 처음에 이중 배열로 들어가다가 numbers 길이 수를 보고 방법을 바꿨습니다. numbers를 이중 배열로 들어가는 최악의 케이스는 100억이기 때문에 보통 백만개 정도가 한계인 n^2의 복잡도로는 타임오버가 되기 때문입니다. 

 

그러면 무조건 nlogn 이하의 복잡도로 구현을 해야 하는데 sort를 쓰는 것밖에 풀이방법이 없었습니다. sort함수로만 구현하려면 기준 함수 작성에서 방법을 찾아야 했고 제가 찾은 해답은 이러했습니다.

 

numbers를 정렬하되 i번 원소와 i + 1번 원소를 연결한 값과 i + 1번 원소와 i번 원소를 연결한 값중 더 큰 값이 앞으로 오도록 정렬합니다.

예를 들어 3과 30이 있다면 330과 303중 더 큰 값은 330이기 때문에 3, 30 으로 정렬이 되어야 합니다.