[Programmers] 가장 큰 수

LinkLv2. 가장 큰 수

  • 문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를

만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여

만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항
  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
numbers return
[6, 10, 2] 6210
[3, 30, 34, 5, 9] 9534330

 

  • 문제 풀이

문제는 명확하고 간단하다.

배열에는 여러 수가 들어 있고 그 숫자를 앞뒤로 배치하여 제일 큰 수를 구하는 것이다.

그런데 숫자를 앞뒤로 적절히 비교하며 배치할 함수를 엉성하게 만들어 생각보다 시간이 많이 걸렸다.

 

처음 생각은, [3, 30, 34, 5, 9] 와 같이 배열이 있을 때

맨 왼쪽 숫자가 크면 무조건 앞에 둬야 한다고 생각했다. 예를들어, 5 는 34 보다 왼쪽이다.

그렇다면 맨 왼쪽 숫자가 같은 3 과 34 일 경우는?

3은 다음 숫자가 없으므로 그대로 3을 가지고 비교하고

34는 다음 수인 4를 가지고 비교하여 34를 보다 왼쪽에 둔다.

343 > 334 보다 크므로 맞다.

이런식으로 비교 했을 때 문제가 없을 줄 알았다. 그런데.. 구멍이 숭숭 뚫린 생각이었다.

예를들어 [34, 3435] 가 있을 경우 위의 경우로 구하면

34는 같으므로 넘어가고 왼쪽 수(34)는 4를 가지고 비교해 나가는데

오른쪽 수(3435)의 다음 수인 3을 비교 했을 때 4가 더 크므로

343435 가 되고 이는 343534보다 작다.

그래서 생각했다. 결국엔, 그냥 앞 뒤로 두 수를 붙여서 비교하는 수 밖에 없다고.

 

[34, 3435]에서 두 수를 앞 뒤로 붙이면 343435와 343534 가 나오며

3435가 더 앞 이므로 두 수의 정렬 상태는 [3435, 34]가 된다.

이런식으로 비교함수를 만들면 문제는 풀린다.

참, 모두 [0, 0, 0] 인 경우가 있으므로 이럴 때 답은 000 이 아닌 0임을 유의하자.

중복을 허용하지 않는다고 문제에서는 말한 적 없다.

시간 복잡도는 정렬비교하는데 걸리는 시간인 BigO(n log n) 쯤이 될 것이다.

 

Souce Code Linkthe_biggest_figure.cpp

“[Programmers] 가장 큰 수”의 5개의 댓글

  1. 요소의 최대값이 1000인데 이경우에도 처음 생각하신 방법에 반례가 있을까요?
    저도 같은 아이디어로 문제를 해결하려고하는데 tc 1~6이 오답이 나와서요.
    최대값이 1000이라 위의 예시는 문제가안되고 반례를 못찾겠어요

    1. 처음 아이디어는 1000 이하도 맞지 않습니다. 반례로 꼽아 보자면.. [35, 354] 이라고 가정 했을 때 처음 아이디어로 하면 35354이 됩니다. 35354 는 반대의 경우인 35435 보다 작으므로 맞지 않습니다.

  2. 첫번째 아이디어 떠올리고 계속 몇 케이스가 틀려서 반례까지 떠올렸는데 도저히 해결법이 안떠올라 검색했습니다. 풀이를 볼때마다 느끼는건데 의외로 답은 간단하네요…

댓글 남기기

%d 블로거가 이것을 좋아합니다: