코딩테스트 문제 (5) - 가장 큰 수

문제 이름이 가장 큰 수로 되어 있지만 당연하게도 배열 중 가장 큰 수를 찾는 문제는 아닙니다. 이 문제는 항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하는 문제입니다.

문제

1. [10,2] => '210', 2. [3,30,34,5,9] => '9534330'

• [10,2] 케이스의 경우 10을 추출하는 것이 아닌 두 원소의 조합 '102'와 '210' 중 더 큰 수를 출력해야 합니다.
• 배열의 원소는 정수입니다.

풀이

[10,2]의 경우 10이 아닌 2가 앞에 위치하도록 정렬해야 합니다. [3,30,34,5,9]의 경우에는 9가 맨 앞에 위치하도록 정렬해야합니다. 이러한 순으로 정렬한 후에 각 원소를 string으로 만들어 join 메소드를 이용해 합치면 될 것 같습니다.

배열의 원소가 정수로 들어왔을 때, 두 개의 원소 조합 중 어떤 조합이 더 큰지를 어떻게 판단할 수 있을까요?

kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다.

• 두 개의 원소 조합 중 어떤 조합이 더 큰지는 swap 함수에 구현되어 있습니다. 해당 원소를 string으로 바꾸고 각 원소의 합으로 a+b와 b+a의 크기를 비교하는 방식입니다. 다른 좋은 방법도 있을 것 같습니다.
• 정렬 방법 중 삽입 정렬을 이용합니다. 삽입 정렬뿐 아니라 병합 정렬, 선택 정렬 등 여러 정렬 방법을 사용하여도 결과는 당연히 같습니다. 문제가 정렬된 array가 아닌 string으로 반환하여야 하므로 병합 정렬을 사용할 경우 약간의 처리가 필요할 수 있겠네요.

홍머스 정리

• 다양한 정렬 사용 가능
• 난이도: 중-하

참조

• <파이썬 알고리즘 인터뷰>, p504-506