[PCCP] Lv2: 가장 큰 수(42746) 해설

문제

- 문제 링크: 가장 큰 수

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: numbers의 길이

- sort()에서 Comparator을 기준으로 정렬. Comparator는 람다식으로 구현. 두 문자열을 조합 후 int형으로 변환하여 비교

- 각 수는 최댓값이 1,000이므로 문자열을 합칠 경우 최대 문자열의 길이는 7

- 데이터가 N개일 때 정렬에 필요한 시간 복잡도는 O(NlogN)

- 최종 시간 복잡도: O(7logN) → O(NlogN)

import java.util.ArrayList;

public class Solution {
    public String solution(int[] numbers) {
        // int형 정수 배열을 문자열로 바꾸어 list에 저장
        ArrayList<String> list = new ArrayList<>();
        for (int number : numbers) {
            list.add(String.valueOf(number));
        }
        
        // 조합해서 비교하여 더 큰 수를 기준으로 내림차순 정렬
        list.sort((o1, o2) -> {
            int a = Integer.parseInt(o1 + o2);
            int b = Integer.parseInt(o2 + o1);
            return Integer.compare(b, a);
        });
        
        // 정렬된 수를 나열하여 문자열로 만듬
        StringBuilder sb = new StringBuilder();
        for (String s : list) {
            sb.append(s);
        }
        
        // 문자열을 반환, 맨 앞에 "0"이 있는 경우는 "0"만 반환
        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: numbers의 길이

- 각 수의 최댓값이 1,000이므로 문자열을 합칠 경우 최대 문자열의 길이는 7

- 데이터가 N개일 경우 정렬: O(NlogN)

- 최종 시간 복잡도: O(7logN) → O(NlogN)

import functools

def compare(a, b):
    # 각 수를 문자열로 바꾼 뒤, 조합해서 비교하여 더 큰 수를 반환
    t1 = str(a) + str(b)
    t2 = str(b) + str(a)
    return (int(t1) > int(t2)) - (int(t1) < int(t2))
    
def solution(numbers):
    # reverse = True를 이용해 내림차순으로 정렬
    sorted_nums = sorted(numbers, key=functools.cmp_to_key(lambda a, b: compare(a, b)), reverse=True)
    
    # 각 정렬된 수를 문자열로 이어붙인 뒤, int로 변환한 값을 문자열로 다시 변환하여 반환
    answer = "".join(str(x) for x in sorted_nums)
    return "0" if int(answer) == 0 else answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: numbers의 길이

- sort()에서 compared()를 기준으로 정렬

- compared()는 두 수를 문자열로 바꾼후 조합해서 비교하는 함수

- 각 수는 최댓값이 1,000이므로 문자열을 합칠 경우 최대 문자열의 길이는 7

- 데이터가 N개 일 때 정렬에 필요한 시간 복잡도: O(NlogN)

- 최종 시간 복잡도: O(7*logN)

function compare(a, b) {
    // 각 수를 문자열로 바꾼뒤 조합하여 비교
    const t1 = a.toString() + b.toString();
    const t2 = b.toString() + a.toString();
    
    return t1 > t2 ? -1 : 1;
}

function solution(numbers) {
    // compare 함수를 이용하여 내림차순으로 정렬
    const sortedNums = numbers.sort(compare);
    // 각 정렬된 수를 문자열로 이어붙인 뒤, int로 변환한 값을 문자열로 다시 변환하여 반환
    const answer = sortedNums.join("");
    
    return Number(answer) === 0 ? "0" : answer;
}

solution 2)

import

solution 3)

import