[Programmers] 가장 큰 수

Link: Lv2. 가장 큰 수

• 문제 설명

 

• 문제 풀이

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

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

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

 

처음 생각은, [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 Link: the_biggest_figure.cpp