179. Largest Number

문제

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

코드

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        List<String> list = new ArrayList<>();
        if(nums.length == 1)
            return String.valueOf(nums[0]);
        list.add(String.valueOf(nums[0]));
        for(int i=1; i<nums.length; i++){
            String curStr = String.valueOf(nums[i]);
            String maxStr = "";
            int maxIdx = -1;
            for(int j=0; j<=list.size(); j++){
                StringBuilder sb = new StringBuilder();

                for(int k=0; k<j; k++)
                    sb.append(list.get(k));
                sb.append(curStr);
                for(int k=j; k<list.size(); k++)
                    sb.append(list.get(k));
                String tmpStr = sb.toString();

                if(maxStr.equals("")){
                    maxStr = tmpStr;
                    maxIdx = j;
                }
                else if(tmpStr.compareTo(maxStr) > 0){
                    maxStr = tmpStr;
                    maxIdx = j;
                }
                // System.out.println("j : " + j + ", maxStr : " + maxStr + ", tmpStr : " + tmpStr + ", maxIdx : "+maxIdx);
            }
            list.add(maxIdx, curStr);
            // System.out.println("i : " + i + ", list : "+ list);
        }
        // System.out.println(list);
        StringBuilder resSb = new StringBuilder();
        for(String str : list)
            resSb.append(str);
        String resStr = resSb.toString();
        if(resStr.charAt(0) == '0')
            return "0";
        return resSb.toString();
    }
}

피드백

• 내 코드는 O(N^3)이다.

  • 가장 큰 경우로 정렬 된 k개의 원소가 있는 리스트가 있을 때 k+1 번째 원소를 각 원소의 사이사이에 넣어 최대가 되는 인덱스에 넣어주는 방식으로 ack를 받았다.

• 근데 얘는 O(nlogn)이다. https://leetcode.com/problems/largest-number/discuss/53158/My-Java-Solution-to-share

  • 소팅을 이용해서 붙이면 최대가 되는 순으로 정렬함... 이건 생각 못했다.
  • leetcode에는 괴물이 산다.