[PCCP] Lv1: 정수 내림차순으로 배치하기(12933) 해설

문제

- 문제 링크: 정수 내림차순으로 배치하기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    vector<int> v;
    while (n){
        v.push_back(n%10);
        n/=10;
    }
    sort(v.begin(), v.end());
    // size_t일 경우 시간 초과
    for (int i = v.size()-1; i >= 0; --i){
        answer *= 10;
        answer += v[i];
    }
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: 주어진 숫자

- 주어진 숫자의 숫자의 자릿 수는 대략 logN이고 이를 배열로 만드는 작업에 필요한 시간 복잡도: O(logN)

- 이후 배열을 sort()로 정렬시 O(logN*log(logN))이 필요하고 다시 문자열로 조합할 때 필요한 시간 복잡도는 logN

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

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public long solution(long n) {
        // 정수 n을 문자열로 변환하고 각 자릿수를 배열로 저장
        String[] digits = String.valueOf(n).split("");
        
        // 내림차순으로 정렬
        Arrays.sort(digits, Collections.reverseOrder());
        
        // 정렬된 숫자를 다시 하나의 문자열로 합침
        StringBuilder sb = new StringBuilder();
        for (String digit: digits)
            sb.append(digit);
        
        // 문자열을 long형으로 변환하여 반환
        return Long.parseLong(sb.toString());
    }
}

solution 2) 계수 정렬 활용

- 시간복잡도는 O(logN)dp rmstk

class Solution {
    public long solution(long n) {
        // 0-9 숫자 수 만큼 빈도수 배열 생성
        int[] counts = new int[10];
        
        // 숫자에 대한 빈도수를 count 배열에 저장
        while (n > 0) {
            counts[(int)(n % 10)]++;
            n /= 10;
        }
        
        // 빈도수 배열을 9부터 0까지 순회하면서 답을 구함
        long answer = 0;
        for (int i = 9; i >= 0; --i) {
            for (int j = 0; j < counts[i]; ++j) {
                answer += i;
                answer *= 10;
            }
        }
        return answer / 10;
    }
}

solution 3)

import java.util.Arrays;

class Solution {
    public long solution(long n) {
        long answer = 0;
        int[] arr = new int[String.valueOf(n).length()];
        int count = 0;
        
        // arr에 자릿수 담기
        while(n > 0) {
            arr[count] = (int)(n % 10);
            n /= 10;
            count++;
        }
        
        // 정렬
        Arrays.sort(arr);
        
        // 문자열에 붙이기
        String s = "";
        for(int i = arr.length - 1; i >= 0; i--) {
            s += arr[i];
        }
        
        answer = Long.parseLong(s);
        
        return answer;
    }
}

 

(Python)

solution 1)

- N: 주어진 숫자

- 주어진 숫자의 자리수는 logN

- list로 만드는 작업에 필요한 시간 복잡도: O(logN)

- list를 다시 sort()로 정렬하는 시간 복잡도: O(logN * log(logN))

- 다시 문자열로 조합: O(logN)

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

def solution(n):
    digits = list(str(n)) # 정수 n을 문자열로 변환하고 각 자릿수를 리스트로 저장
    digits.sort(reverse=True) # 내림차순으로 정렬
    answer = int("".join(digits)) # 정렬된 자릿수를 다시 하나의 문자열로 합쳐 정수로 변환
    
    return answer

solution 2)

def solution(n):
    answer = 0
    answer = sorted(list(str(n)), reverse=True)
    answer = int("".join(answer))
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: 주어진 숫자

- 주어진 숫자의 자릿수(logN)을 배열로 만드는 작업: O(logN)

- 배열을 sort()로 정렬: O(logN*log(logN))

- 다시 문자열로 조합: O(logN)

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

function solution(n) {
    // 정수 n을 문자열로 변환하고 각 자릿수를 배열로 저장
    const digits = Array.from(String(n), Number);
    digits.sort((a, b) => b - a); // 내림차순으로 정렬
    
    // 정렬된 자릿수를 다시 하나의 문자열로 합쳐 정수로 변환
    const answer = Number(digits.join(''));
    console.log(Array.from(String(n), Number))
    return answer;
}

solution 2)

function solution(n) {
  return parseInt((n+"").split("").sort().reverse().join(""));
}

solution 3)

import