Largest Number(Array,String,Greedy,Sorting)

https://leetcode.com/problems/largest-number/description/

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

 

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

문제 자체는 일단 설명이 짧아서 좋다.

 

한 번 Deep into it 해보자!

 

1. Python

하.. 피터지게 싸웠지만 기본 test case만 통과하고 다른 test case에선 오답이었다.

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        ans = ""
        # make them all string
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        while nums:
            temp = '0'
            for x in nums:
                if x[0] > temp[0]:
                    temp = x
                elif x[0] == temp[0]:
                    idx = 0
                    cond = True
                    n1 = len(x)
                    n2 = len(temp)
                    while idx < n1 and idx < n2:
                        if x[idx] > temp[idx]:
                            temp = x
                            cond = False
                            break
                        idx+=1
                    if cond:
                        if len(x) > len(temp):
                            if x[idx] > x[0]:
                                temp = x
                        else:
                            if temp[idx] < x[0]:
                                temp = x
            ans+=temp
            nums.remove(temp)

        return ans

 

2차 수정안..

 

아 왜 안 되냐 ㅠㅠ

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        ans = ""
        # make them all string
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        while nums:
            temp = '0'
            for x in nums:
                if x[0] > temp[0]:
                    temp = x
                elif x[0] == temp[0]:
                    if x == temp : continue

                    idx = 0
                    cond = True
                    n1 = len(x) # 830 , 1113
                    n2 = len(temp) # 8308 , 111311
                    while idx < n1 and idx < n2:
                        if x[idx] > temp[idx]:
                            temp = x
                            cond = False
                            break
                        idx+=1
                    if cond:
                        if len(x) > len(temp):
                            if x[idx:] + temp > x :
                                temp = x
                        else:
                            if temp[idx:]+x < temp :
                                temp = x
            ans+=temp
            nums.remove(temp)

        return ans

 

미치겄네 뭘 놓친거야

 

아 현타온다..

 

답을 보고야 말았다.

 

요즘 스트레스 받나.. 왜이렇게 문제를 어렵게만 생각했지

 

하나는 알고 둘은 몰랐더니 먼 길 돌아갔다 ㅠㅠ

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # 모든 숫자를 문자열로 변환
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        
        # 결과 문자열
        ans = ""
        
        while nums:
            temp = nums[0]  # 기본적으로 첫 번째 값을 temp로 설정
            for x in nums:
                # x + temp와 temp + x를 비교하여 더 큰 조합을 선택
                if x + temp > temp + x:
                    temp = x
            
            # ans 업데이트
            ans += temp
            nums.remove(temp)
        
        # 결과가 '0'으로 시작하면 '0' 반환
        return '0' if ans[0] == '0' else ans

 

 

밑에는 억울해서 결국 풀어낸 개 주접 코드...

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        ans = ""
        # make them all string
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        while nums:
            temp = '0'
            for x in nums:
                if x[0] > temp[0]:
                    temp = x
                elif x[0] == temp[0]:
                    if x == temp : continue

                    idx = 0
                    cond = True
                    n1 = len(x) # 830 , 1113
                    n2 = len(temp) # 8308 , 111311
                    while idx < n1 and idx < n2:
                        if x[idx] > temp[idx]:
                            temp = x
                            cond = False
                            break
                        elif x[idx] < temp[idx]:
                            cond = False
                            break
                        idx+=1
                    if cond:
                        if len(x) > len(temp):
                            if x+temp > temp+x :
                                temp = x
                        else:
                            if temp+x < x+temp :
                                temp = x
            if ans != '0':
                ans+=temp
            nums.remove(temp)

        return ans

 

C++로는 다음과 같다..

 

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        string ans = "";
        // make thnem to string
        vector<string> vec;
        for(const int x : nums){
            vec.push_back(to_string(x));
        }

        while(!vec.empty()){
            string temp = vec[0];
            for(const string y: vec){
                if(y+temp > temp+y) temp = y;
            }
            ans += temp;
            auto it = find(vec.begin(),vec.end(),temp);
            vec.erase(it);
        }
        return ans[0]=='0' ? "0" : ans;
    }
};