오늘은 programmers의 가장 큰 수 문제를 풀어봤다. 문제를 간단히 설명해 보자면, 0 또는 양의 정수가 여러개 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 구하는 것이다.
처음 이 문제를 보았을 때 "조합"을 생각했다. 재귀를 이용하여 배열 안에 있는 숫자들을 조합하다 보면 가장 큰 수를 구할 수 있을 것이라고 생각했다.
하지만 문제의 제한사항을 보면 배열의 길이는 1에서 100,000 이하라는 것을 알 수 있다. 100,000개의 숫자를 조합하면 시간초과가 난다는 것을 예상할 수 있다. 그래서 다른 방법을 생각해 보았다.
이 문제의 핵심은 "정렬을 어떤 방식으로 할 것인가?" 이다. 배열 안에 있는 정수들을 단순히 내림차순으로 정렬한다고 해도 이 정수들을 이어 붙였을 때 가장 큰 정수가 된다는 보장은 할 수 없다. 예를 들어 [3, 30, 34, 5, 9]
은 정렬하면 [34, 30, 9, 5, 3]
이기 때문에 이를 이어붙인 "3430953"
은 가장 큰 수가 아니다.
그렇다면 유니코드를 기준으로 정렬해보면 되지 않을까? javascript의 sort()
함수는 요소의 순서를 결정하는데 사용되는 함수를 정의하지 않는다면 기본적으로 문자열의 유니코드 코드 포인트를 따른다.
따라서 [3, 30, 34, 5, 9]
의 경우 [9, 5, 34, 30, 3]
이 된다. 하지만 이것도 이어 붙인다면 "9534303"
이 되지만, 실제 정답은 "9534330"
이므로 틀린 답이 된다.
위 결과를 토대로 생각해보면 "9534303"
-> "9534330"
이 되기 위해서는 3과 30의 위치만 바뀌면 된다. 3과 30은 330
과 303
두 가지 중 하나가 될 수 있다. 그렇다면 나머지 숫자들도 두 개의 숫자를 문자열로 이어 붙여 크기를 비교하고 위치를 바꿀지 안바꿀지 결정하면 되지 않을까? 두 숫자를 a, b라 한다면 문자열 ab와 ba를 비교하면 된다는 말이다.
const solution = (numbers) => {
const answer = numbers
.sort((a, b) => (`${a}${b}` - `${b}${a}` > 0 ? -1 : 1))
.join("");
};
sort()
내부의 함수는 -1 이면 순서를 바꾸고 1이면 바꾸지 않는다. 이에 대한 결과로 나온 배열에 join("")
을 적용하여 하나의 문자열로 이어 붙여 반환하면 된다.
하지만 하나의 예외 케이스가 해결되지 않았다. [0,0,0,0]
같은 경우는 위 코드대로 하면 "0000"
이 된다.
이 문제는 숫자를 문자열로 바꿔야 하기 때문에 "0000"
은 "0"
이 되어야 한다. 따라서 이 부분에 대한 예외만 추가해준다면 문제를 풀 수 있다.
const solution = (numbers) => {
const answer = numbers
.sort((a, b) => (`${a}${b}` - `${b}${a}` > 0 ? -1 : 1))
.join("");
return answer[0] === "0" ? "0" : answer;
};
test("solution", () => {
expect(solution([6, 10, 2])).toBe("6210");
expect(solution([3, 30, 34, 5, 9])).toBe("9534330");
expect(solution([9, 90, 99, 19, 91])).toBe("999919019");
expect(solution([999, 99, 9, 9, 9])).toBe("99999999");
expect(solution([10, 6, 10, 6])).toBe("661010");
expect(solution([0, 1000])).toBe("10000");
expect(solution([0, 99, 1000])).toBe("9910000");
expect(solution([1, 2, 35, 4, 5])).toBe("543521");
expect(solution([0, 0, 0, 0])).toBe("0");
});
github : https://github.com/Kwakcena/daily-ps/tree/master/05-May/0526