7. 가장 큰 수 ⁂

https://programmers.co.kr/learn/courses/30/lessons/42746

많은 사람들이 푼 문제입니다만..
이 많은 사람들이 이 문제를 스스로 풀었을까? 의문이 생깁니다. 
평범하지 않은 풀이에 아주 많은 정답자가 있는 걸 봐도...

코딩테스트 연습 - 가장 큰 수

파이썬

단순하게 주어진 조건에 따라 코딩해 봅니다. 

def solution(numbers):
    numbers = list(map(str, numbers))
    max_num = 0
    for i in range(0, len(numbers)-1):
        for j in range(i+1, len(numbers)):
            numbers[i], numbers[j] = numbers[j], numbers[i]
            if int(''.join(numbers)) < max_num:
                numbers[i], numbers[j] = numbers[j], numbers[i]
    return str(int(''.join(numbers)))

이터툴즈(itertools)를 사용할 수도 있습니다. 

def solution(numbers):
    from itertools import permutations
    temp_list = []
    for element in permutations(map(str, numbers)):
        temp_list.append(''.join(element))
    return str(max(map(int, temp_list)))

더 짧게 줄일 수도 있습니다. 

def solution(numbers):
    from itertools import permutations
    return str(max(map(int, [''.join(i) for i in permutations(map(str, numbers))])))

하지만 시간 초과가 나옵니다.
모든 경우의 수를 조사하는 방식으론 통과할 수 없습니다. 

파이썬 2에서는 사용자 지정 비교함수를 위해 cmp라는 매개 변수가 있었는데, 파이썬 3에서는 사라졌습니다.
대신 파이썬 3.2에서, functools.cmp_to_key() 함수가 표준 라이브러리의 functools 모듈에 추가되었습니다.
저는 직접 퀵소트를 구현해서 풀긴 했습니다만, 소스도 복잡하고, 또 파이썬은 재귀의 한계도 있으니 내장된 정렬 함수를 이용합시다.  

def compare(a, b):
    return int(b + a) - int(a + b)


def solution(numbers):
    from functools import cmp_to_key
    numbers = map(str, numbers)  # [str(num) for num in numbers]
    numbers = sorted(numbers, key=cmp_to_key(compare))
    return str(int("".join(numbers)))

정석적인 풀이겠지요?문자열을 앞 뒤로 놓고 숫자로 변환해서 크기를 비교하는데 
ex) '3'과 '30'이 있으면 330이 303보다 크죠. 

의미 없는 줄이기...

def solution(numbers):
    from functools import cmp_to_key
    return str(int("".join(sorted(map(str, numbers), key=cmp_to_key(lambda a, b: int(b + a) - int(a + b))))))

'''
테스트 1 〉	통과 (1213.92ms, 63.1MB)
테스트 2 〉	통과 (463.31ms, 36.6MB)
테스트 3 〉	통과 (1921.11ms, 80.2MB)
'''

이걸 아주 멋지게 푼 분도 계시더라구요. (속도마저 빠름)

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

이 분은 30 보다 3이 크다는 것을 문자열의 반복으로 해결하셨네요. 
ex) '333' > '303030' 문자열일 때는 이렇게 됩니다. 와우~!
사전 순서라고 생각하시면 됩니다. 333이 303보다 뒤(=크)죠. ^^ 리버스로 돌려주고..  
문제 조건에 1000 이하라고... 했기 때문에 *3만 해도 비교가 되죠. 
ex) '100100100' > '100010001000' 
ex) '111' > '100010001000' 

한 줄로 줄인다면 이렇게 되겠죠.
리스트를 쓰지 않아도 iterable 한 상태라 불필요한 list는 제거했습니다. 
그리고 sorted()는 리스트 뿐만 아니라 iterable한 것들은 다 받아줍니다. 
그리고 sorted()는 함수형 프로그램에서 흐름을 끊지 않습니다. (=으로 사용할 수 있다면 흐름이 연결됩니다.)
'파이썬 sort sorted 차이'를 구글에서 검색해보세요. 

def solution(numbers):
    return str(int(''.join(sorted(map(str, numbers), key=lambda x: x*3, reverse=True))))
    
'''
테스트 1 〉	통과 (793.83ms, 61.6MB)
테스트 2 〉	통과 (244.33ms, 36.6MB)
테스트 3 〉	통과 (1348.07ms, 79.9MB)
'''

 

자바스크립트

function solution(numbers) {
    numbers = numbers.map(function (x) {
        return x + '';
    }).sort(function (x, y) {
        if (x + y < y + x) return 1;
        else if (x + y > y + x) return -1;
        else return 0;
    })
    return (numbers[0] == '0') ? '0' : numbers.join('');
}
/*
테스트 1 〉	통과 (101.12ms, 53.9MB)
테스트 2 〉	통과 (58.23ms, 52.8MB)
테스트 3 〉	통과 (121.30ms, 45.2MB)
*/

엄청난 속도군요. 자바스크립트 의외 입니다. 

함수형으로 줄여보겠습니다. (조금 느려지네요.)

function solution(numbers) {
    numbers = numbers.map((x) => x + '')
        .sort((x, y) => (y + x) * 1 - (x + y) * 1)
    return (numbers[0] == '0') ? '0' : numbers.join('');
}
/*
테스트 1 〉	통과 (136.07ms, 52.7MB)
테스트 2 〉	통과 (77.35ms, 52MB)
테스트 3 〉	통과 (177.85ms, 45.4MB)
*/

자바

import java.util.stream.Collectors;
import java.util.stream.IntStream;


class Solution {
    public String solution(int[] numbers) {
        return (IntStream.of(numbers).sum() == 0) ? "0" :
                IntStream.of(numbers)
                        .mapToObj(String::valueOf)
                        .sorted((a, b) -> (b + a).compareTo(a + b))
                        .collect(Collectors.joining());
    }
}

코틀린

이건 자바도 아니고 코틀린도 아녀 ㅠ,.ㅠ

import java.util.stream.Collectors
import java.util.stream.IntStream

class Solution {
    fun solution(numbers: IntArray): String {
        return if (IntStream.of(*numbers).sum() == 0) "0" else IntStream.of(*numbers)
            .mapToObj { i: Int -> i.toString() }
            .sorted { a: String, b: String -> (b + a).compareTo(a + b) }
            .collect(Collectors.joining())
    }
}

C#

using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public string solution(int[] numbers) => 
        (numbers.Max() == 0) ? "0"
        : string.Join("", numbers.Select(x => x.ToString()).OrderBy(x => x, new MyComparer()));
}

public class MyComparer : IComparer<string>
{
    public int Compare(string a, string b) => (b + a).CompareTo(a + b);
}

GO

import (
	"sort"
	"strconv"
)

type Compare []string

func (s Compare) Len() int {
	return len(s)
}
func (s Compare) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func (s Compare) Less(i, j int) bool {
	return s[j]+s[i] < s[i]+s[j]
}
func solution(numbers []int) string {
	var temp []string
	var answer string
	for _, v := range numbers {
		temp = append(temp, strconv.Itoa(v))
	}
	sort.Sort(Compare(temp))
	for _, v := range temp {
		answer += v
	}
	if answer[0] == '0' {return "0"}
	return answer
}

/*
테스트 1 〉	통과 (1114.36ms, 74MB)
테스트 2 〉	통과 (364.91ms, 43.4MB)
테스트 3 〉	통과 (1876.05ms, 98.1MB)
*/

고언어의 문자열의 비교(>, <)는 사전식입니다. 
http://ehpub.co.kr/tag/%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%B9%84%EA%B5%90/

고 언어에서 소트시 사용자 정의 비교 함수를 이용하기 위해서는 고 언어의 상속구조, 인터페이스를 알아야 합니다. ㅠ,.ㅠ 
http://pyrasis.com/book/GoForTheReallyImpatient/Unit54/01

뭐 몰라도 이런 템플릿을 보고 만들면 됩니다.
mingrammer.com/gobyexample/sorting-by-functions/