가장 큰 수 만들기

출처 : http://www.programcreek.com/2014/02/leetcode-largest-number-java/

음수가 아닌 수들이 주어졌을 때 그 수들을 이어서 만들 수 있는 가장 큰 수를 구하시오. 예를 들어 [1,2,3]이 주어졌을 때 만들 수 있는 가장 큰 수는 321이고, [3, 30, 34, 5, 9] 가 주어지면 만들 수 있는 가장 큰 수는 9534330이다.

2016/02/02 23:27

상파

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

39개의 풀이가 있습니다. 1 / 4 Page

def largestnumber(ns):
    ns = map(str,ns)
    ns.sort(cmp=lambda x,y:cmp(x+y,y+x),reverse=True)
    return ''.join(ns)
print largestnumber([3,30,34,5,9])

2016/02/05 19:09

상파

ns.sort(cmp=lambda x,y:cmp(x+y,y+x),reverse=True)에서 cmp(x+y,y+x) 부분이 에러가 나오네요.. 파이썬 3.5를 사용합니다. - hana11, 2016/02/06 11:24 M D
아.. 파이썬 2.7입니다;; - 상파, 2016/02/06 14:31 M D
이런 방법이! 많이 배우고 갑니다^^ - 디디, 2016/03/24 13:27 M D
+1 <파이썬2.7> ns.sort(cmp=lambda x,y:cmp(x+y,y+x),reverse=True) <파이썬3.4> ns.sort(key=functools.cmp_to_key(lambda x,y: int(x+y)-int(y+x)), reverse=True) 이렇게 하면 파이썬 3.4에서 잘 되네요^^ - 디디, 2016/04/01 18:24 M D
알고리즘을 알려주신 '상파'님과 functools.cmp_to_key 메소드를 알려주신 '디디'님께 고마움을 표합니다. - 예강효빠, 2017/05/23 11:40 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from random import shuffle


def largest(L):
    """
    Return the largest int that can be made from L.

    @type L: list[int]
    @rtype: int

    >>> largest([1, 2, 3])
    321
    >>> largest([3, 30, 34, 5, 9])
    9534330
    """

    i = 0
    ass = 0
    while i != 10000:
        temporary_value = "".join(str(x) for x in L)
        if int(temporary_value) >= int(ass):
            ass = int(temporary_value)
        shuffle(L)
        i += 1

    return ass

미적분 시험이 있는 저의 멘붕상태를 코드로 표현했습니다.

코드에서.. '에라, 모르겠다. 될대로 되라'가 느껴져요.. - 상파, 2016/02/05 19:14 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

숫자를 스트링으로 만들고 우선순위를 이용하여 정렬하였습니다.

서로 다른 자리의 수를 비교하기 위해 자리수를 맞추고, 남는 부분을 첫째 짜리 숫자로 채웠습니다.

def largest_number(nums):
    nums_str = [str(x) for x in nums]
    longest = max(len(x) for x in nums_str)
    nums_str.sort(reverse=True,
                  key= lambda x: ('{0:'+str(x[0])+'<'+str(longest)+'}').format(x))
    return ''.join(nums_str)

if __name__ == '__main__':
    print(largest_number([3, 30, 34, 5, 9]))
+2 음... 지금 예제에서는 물론 결과가 맞게 나오지만, 만약 57, 575 수가 있다면 이 방법으로 되지 않네요. 앞자리를 채운다면 정렬시엔 같은 수가 되지만, 결과 57575와 57557은 다르니까요. 제일 뒷자리로 채운다 해도 173, 17 같은 수 경우엔 17173이 되지만 더 큰수는 17317이구요. 저는 뒷자리로 풀이를 해보다 다른 방법이 필요할것 같아서 남깁니다.. - 이 우람, 2016/02/08 22:30 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

# join결과로 역정렬
m_sort = ->nums { nums.sort{|x,y|[y,x].join<=>[x,y].join}.join.to_i }
# 개선 : join 줄이기
p nums.sort{|x,y|[y,x]*''<=>[x,y]*''}*'' #=> "9534330"

Test

nums = [3,30,34,5,9]
expect(m_sort[nums]).to eq 9534330
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Tcl/tk 입니다. sort를 쓰지말라는 말이 없어서 sort로 해봅니다.

set num [ list 3 30 34 5 9 ]
puts [ join [ lsort -integer -decreasing $num ] "" ]
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

var array = [ 57, 589, 51, 5, 10, 20, 30, 44, 509, 5001, 32, 31, 6, 19, 1234 ]

    array.sortInPlace { (obj1, obj2) -> Bool in

        let s1 = String.init(format: "%d", obj1)
        let s2 = String.init(format: "%d", obj2)

        let strlen1 = s1.lengthOfBytesUsingEncoding(NSUTF8StringEncoding)
        let strlen2 = s2.lengthOfBytesUsingEncoding(NSUTF8StringEncoding)

        let mmax = max(strlen1, strlen2)
        let mmin = min(strlen1, strlen2)

        let lastNum1 = obj1 % 10
        let lastNum2 = obj2 % 10

        var num1 = obj1
        var num2 = obj2

        let diff = mmax - mmin
        for(var i = 0; i<diff; ++i) {

            if(strlen1 > strlen2)
            {
                num2 = num2 * 10 + lastNum2
            }
            else
            {
                num1 = num1 * 10 + lastNum1
            }

        }

        return num1 > num2
    }

    print(array) // [6, 589, 57, 5, 51, 509, 5001, 44, 32, 31, 30, 20, 19, 1234, 10]

2016/02/27 18:55

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

python 3.5

def make_largest_number(number_list):
    digit_list = []
    result = ''
    for num in number_list:
        if len(str(num)) > 1:
            for x in str(num):
                digit_list.append(int(x))
        else:
            digit_list.append(num)
    digit_list.sort()
    digit_list.reverse()
    for digit in digit_list:
        result += str(digit)
    return int(result)


print(make_largest_number([1,2,3]))
print(make_largest_number([3, 30, 34, 5, 9]))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from math import *

while __name__ == '__main__':
    li = list(map(int, input("\n수 입력: ").split()))
    순서, 자릿수, 정렬_후 = ([],[],[])
    for i in li:
        자릿수.append(log10(i))
    자릿수 = int(max(자릿수))
    비교_리스트 = []
    for i in range(len(li)):
        비교_리스트.append(li[i]*10**int(자릿수- int(log10(li[i]))))

    정렬_리스트 = list(비교_리스트)
    정렬_리스트.sort()
    for i in range(len(정렬_리스트)):
        순서.append(비교_리스트.index(정렬_리스트.pop()))
    for i in range(len(li)):
        정렬_후.append(li[순서[i]])

    for i in list(map(str, 정렬_후)):
        print(i, end='')

파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def input_numbers():
    list=[]
    while True:
        number = input("Input number : ")
        if(number<0) :
            break
        list.append(number)
    return list

def largest_number(list):
    result=""
    for i in range(0, len(list)):
        for j in range(0, len(list)-1-i):
            ltr = str(list[j])+str(list[j+1])
            rtl = str(list[j+1])+str(list[j])
            if(ltr<rtl):
                tmp=list[j]
                list[j]=list[j+1]
                list[j+1]=tmp

    for i in list:
        result+=str(i)

    print(result)


largest_number(input_numbers())

2016/03/23 17:02

082

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

082님께서 지적해주셨는데, 30, 31, 32 는 3보다 실질적으로 작다고 평가되어야 하네요. 파이썬3부터는 sorted 함수에 임의의 비교 함수를 쓸 수가 없어서 정렬함수를 새로 만들었습니다.


def do(numbers):
    def mySort(xs):
        if len(xs) < 1:
            return xs
        p = xs[0]
        l = [x for x in xs[1:] if x+p > p+x]
        r = [x for x in xs[1:] if x+p <= p+x]
        return mySort(l) + [p] + mySort(r)
    return int(''.join(mySort([str(x) for x in numbers])))

print(do([3, 30, 34, 5, 9]))
#9534330
+1 출력 결과가 9534303 로 나옵니다. 9534330 으로 나와야 합니다 - 082, 2016/03/24 10:24 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 39
python x 22
ruby x 2
기 타 x 6
java x 5
php x 2
cpp x 1
javascript x 1