[programmers] 가장 큰 수

곽형조 (KCena)·2020년 5월 27일
0

가장 큰 수 문제 풀이

오늘은 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은 330303 두 가지 중 하나가 될 수 있다. 그렇다면 나머지 숫자들도 두 개의 숫자를 문자열로 이어 붙여 크기를 비교하고 위치를 바꿀지 안바꿀지 결정하면 되지 않을까? 두 숫자를 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

0개의 댓글