가장 큰 수 / java / 정렬

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

입출력 예

 

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

 

---

Java Comparable, Comparator

Comparable, Comparator하면 '정렬'을 떠올려야하는 것이다.

 

우선 자바에서 객체를 정렬할 때 일정한 기준이 필요하다.

 

Comparable : 객체 간의 일반적인 정렬이 필요할 때, Comparable 인터페이스를 확장해서 정렬의 기준을 정의하는 compareTo() 메서드를 구현한다.

Comparator : 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다.

 

공통점은 정렬의 기준을 정의한다는 것이고,

 

차이점은 정렬 기준이

-일반적이냐 일반적이지 않냐와

-compareTo(Object o) 메서드를 구현하느냐 compare(Object o1, Object o2) 메서드를 구현하느냐

 

Comparable 구현

Student Vo를 생성하여 Comparable 인터페이스를 구현하였다. Comparable 인터페이스를 구현하는 경우

public int compareTo(T) 메소드를 구현하고 내부에서 비교처리 후 int형 리턴으로 비교 결과를 리턴한다.

• 양수리턴 : this 오브젝트가 앞에 위치
• 음수리턴 : this 오브젝트가 뒤에 위치
• 0리턴 : 동일한 값으로 간주하고 입력 순서 유지

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

public class Student implements Comparable<Student> {          private String name;     private int age;          public Student(String name, int age) {         this.name = name;         this.age = age;     }            public String getName() {         return name;     }          public int getAge() {         return age;     }          /**      * 양수가 리턴 되는 경우 현재 Object가 앞      * 음수가 리턴 되는 경우 현재 Object가 뒤      * 0이 리턴되는 경우 동일 값으로 간주하고 입력순서 유지      */     @Override     public int compareTo(Student o) {         int result = this.getName().compareTo(o.getName());         if(result == 0) {             result = this.getAge() - o.getAge();         }         return result;     } } Colored by Color Scripter

cs

 

아래와 같이 테스트를 수행하는 경우

1 2 3 4 5 6 7 8 9 10 11 12

public static void main(String[] args) {     Student s1 = new Student("홍길동", 27);      Student s2 = new Student("이지수", 31);      Student s3 = new Student("이지수", 30);     Student[] arr = new Student[]{s1, s2, s3};          Arrays.sort(arr);          for(Student s : arr) {         System.out.println(s.getName() + " " + s.getAge());     } } Colored by Color Scripter

cs

 

이렇게 이름순으로 먼저 정렬되고, 이름이 같은 경우 나이순으로 정렬된 결과를 얻는다.

 

이지수 30
이지수 31
홍길동 27

 

Comparator 구현

Comparator는 보통 다음과 같은 상황에서 사용된다.

1. JAVA에서 기본제공하는 Reference Type을 내가 원하는대로 정렬하고 싶을때 (예시 : String, Integer를 역순으로 정렬 혹은 특정추가 조건)
2. 기존에 구현된 Comparable의 정렬과는 다른 결과를 얻고 싶을 때

즉 기존에 구현되어 있는 Comparable 인터페이스 구현 대신에 다른 조건에 의해서 정렬하고자 하는 경우 사용된다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public static void main(String[] args) {     Student s1 = new Student("홍길동", 27);      Student s2 = new Student("이지수", 31);      Student s3 = new Student("이지수", 30);     Student[] arr = new Student[]{s1, s2, s3};          Arrays.sort(arr, new Comparator<Student>() {         @Override         public int compare(Student o1, Student o2) {             return o1.getAge() - o2.getAge();         }     });          for(Student s : arr) {         System.out.println(s.getName() + " " + s.getAge());     } } Colored by Color Scripter

cs

 

Arrays.sort() 혹은 Collections.sort()에 두번째 인자로 Comparator 구현체를 전달하여 주면 된다.

홍길동 27
이지수 30
이지수 31

출처: https://javaplant.tistory.com/15 [자바공작소]

Comparator 함수를 찾아보다가 정리해본다.. 자바는 끝이없고..

 

---

 

내가 짠 코드

import java.util.*;


class Solution {
    public String solution(int[] numbers) {
        String answer = ""; // 리턴값 초기화
        String[] str_numbers = new String[numbers.length]; // 파라미터 numbers 배열의 길이와 같은 string 배열을 생성
        // int 배열인 numbers를 string배열인 str_numbers로 변환
        for (int i = 0 ; i < numbers.length ; i++) {
            str_numbers[i] = String.valueOf(numbers[i]);
        }
        // str_numbers를 Compare()에 정의된 방식으로 정렬
        Arrays.sort(str_numbers, new Compare());
        // 현재 str_numbers는 올림차순으로 정렬되어 있음
        // 따라서 가장 마지막 인덱스의 값이 max값이고, 이것이 반환값의 가장 앞에 올 숫자임
        // 반환값의 맨 앞 숫자가 0이면 answer=0 
        // 반환값의 맨 앞 숫자가 0이 아니면 내림차순으로(가장 큰 수부터) answer에 담음
        if (str_numbers[str_numbers.length - 1].equals("0")) {
            answer += "0";
        } else {
            for (int i = str_numbers.length - 1; i >= 0; i--) {
                // Compare 클래스에서 올림차순 정렬을 했다면 아래 코드 사용
                // for(int i = 0 ; i < str_numbers.length ; i++)
                answer += str_numbers[i];
            }
        }
        return answer;
    }
}
// Comparator 인터페이스를 오버라이딩하여 정렬 방식을 재정의하기
class Compare implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return (o1 + o2).compareTo(o2 + o1);// 올림차순 정렬
        
        // 내림차순 정렬은 아래와 같이 순서를 바꾸어주면 된다
        // return (o2 + o1).compareTo(o1 + o2);
    }
}

 

다른 사람이 짠 코드(콜렉션 함수 사용)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++) {
            list.add(numbers[i]);
        }
        Collections.sort(list, (a, b) -> {
            String as = String.valueOf(a), bs = String.valueOf(b);
            return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
        });
        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}