(알고리즘 스터디) 8주차 금_Sort🚦_(Programmers) 가장 큰 수

🌟 프로그래머스 / Sort / Level 2 / 가장 큰 수

📃 문제

프로그래머스

🚫 제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

👀 입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

🤔 풀이 방법

➡️ 버블 정렬 (= 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘) 로 조합을 비교해가면서 순서를 결정한다.

ex) [6, 10, 2]
① 6 과 10 비교 ➡️ 610 > 106 ➡️ 순서 유지 / [6, 10, 2]
② 10 과 2 비교  ➡️ 102 < 210 ➡️ 순서 바꾸기 / [6, 2, 10]
(첫번째 turn 종료)
③ 6 과 2 비교 ➡️ 62 > 26 ➡️ 순서 유지 / [6, 2, 10] (최종)
④ 문자열 결합 ➡️ answer = "6210"

💻 풀이 코드

1️⃣ 방법 ① : 일반 정렬로 구현

class Solution {
    public static void main(String[] args) {
        String answer = "";

        // 풀이 순서 : 숫자 배열 -> 문자 배열 -> 정렬 -> 문자열
        
        // (1) 숫자 배열 -> 문자 배열
        String[] strNumbers = new String[numbers.length];

        for (int i=0; i<numbers.length; i++) {
            strNumbers[i] = "" + numbers[i];
        }

        // (2)-1 버블 정렬
        for (int i=1; i<strNumbers.length; i++) {
            for (int j=0; j<strNumbers.length-i; j++) {
                String s1 = strNumbers[j];
                String s2 = strNumbers[j+1];
                if ((s1+s2).compareTo(s2+s1) < 0) {
                    strNumbers[j+1] = s1;
                    strNumbers[j] = s2;
                }
            }
        }
        
        // (3) 문자열로 변환
        for (String str : strNumbers) {
            answer += str;
        }

        return answer;
    }
]

2️⃣ 방법 ② :  Comparator 활용

class Solution {
    String answer = "";
    
    String[] strNumbers = new String[numbers.length];

    for (int i=0; i<numbers.length; i++) {
        strNumbers[i] = "" + numbers[i];
    }

    // (2)-2 Comparator 활용
    Arrays.sort(strNumbers, new Comparator<String>() {
        public int compare(String o1, String o2) {
            // return (o1+o2).compareTo(o2+o1); // 오름차순
            return (o2+o1).compareTo(o1+o2); // 내림차순
        }
    });

    for (String str : strNumbers) {
        answer += str;
    }
    return answer;
}

3️⃣ 방법 ③ : Comparator + 람다식 활용

class Solution {
    String answer = "";

    // (1) 숫자 배열 -> 문자 배열
    String[] strNumbers = new String[numbers.length];

    for (int i=0; i<numbers.length; i++) {
        strNumbers[i] = "" + numbers[i];
    }

    // (2)-3 Comparator + 람다식 활용
    Arrays.sort(strNumbers, ((o1, o2) -> (o2+o1).compareTo(o1+o2)));

    for (String str : strNumbers) {
        answer += str;
    }
    
    return answer;
}

4️⃣ 방법 ④ : Stream 활용

import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
    public String solution(int[] numbers) {
        String answer = IntStream.of(numbers)
            .mapToObj(n->String.valueOf(n))
            .sorted((s1,s2)->(s2+s1).compareTo(s1+s2))
            .collect(Collectors.joining());

        if (answer.startsWith("0")) answer = "0";
        
        return answer;
    }
}

 

[level 2] Title: 가장 큰 수, Time: 5.10 ms, Memory: 65.6 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@e1fe9db