[Level 1] 정수 내림차순으로 배치하기

- 방법은 많다...!

 

문제

"함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다."

 

제한 조건

• n은 1이상 8000000000 이하인 자연수입니다.

입출력 예

n	return
118372	873211

 

Long으로 받은 변수를 문자열로 치환해 내림차순으로 변경한 후에 다시 타입 변환해서 반환할 생각이었다.

내림차순으로 변경하는 방법은 (함수를 몰라서) 배열이 오름차순으로 정렬되어 있으니 뒤에서 차례로 꺼내 다시 저장하는 것으로 정했다. 

 

풀이

import jaga.util.Arrays;

class Solution{
   public long solution(long n){
       String[] nStr = String.valueOf(n).split(""); //1
       Arrays.sort(nStr); //2
       
       StringBuilder sb = new StringBuilder(); //3
       
       for(int i = nStr.length-1; i >= 0; i--){ //4
           sb.append(nStr[i]); 
       }
       
       return Long.parseLong(sb.toString()); //5
   }
}

 

1. long 변수를 String으로 변환 한 후 문자열을 분할한다.

2. 분할 된 문자열을 Arrays.sort()를 사용해 오름차순으로 정렬한다.

3. StringBuilder를 생성한다.

4. 오름차순으로 정렬된 배열을 뒤에서부터 StringBuilder에 붙여 내림차순이 되게 해준다.

5. 내림차순으로 정렬한 StringBuilder를 long으로 변환시킨 후 반환한다. 

 

다른풀이

위에 내가 푼 풀이에서 4번은 필요 없는 코드이긴 하다.

Arrays.sort() 또는 StringBuilder에 정렬 기능이 있기 때문이다.

 

Arrays.sort()를 사용할 경우 Collections.reverseOrder()를 사용하면 내림차순으로 정렬할 수 있다.

 

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

class Solution{
   public long solution(long n){
       String[] nStr = String.valueOf(n).split(""); 
       Arrays.sort(nStr, Collections.reverseOrder()); 
       
       StringBuilder sb = new StringBuilder(); 
       
       for(String s : nStr){ 
           sb.append(s); 
       }
       
       return Long.parseLong(sb.toString());
   }
}

 

주의할 점은 Collections.reverserOrder는 Object 배열에만 사용 가능하고 기본타입 배열에서는 오류가 난다. Collection 자체가 객체를 다루는 클래스이기 때문이지 않을까 싶다. 나는 String 배열이었기 때문에 오류 없이 사용 가능했지만, 만일 char 타입으로 배열을 만들었을 경우 Arrays.sort()로 내림차순은 불가능하다.

 

StringBuilder를 활용해서 정렬할 수도 있다.

 

import java.util.Arrays;

class Solution{
   public long solution(long n){
       String[] nStr = String.valueOf(n).split(""); 
       Arrays.sort(nStr); //1
       
       StringBuilder sb = new StringBuilder(); 
       for(String s : nStr){ //2
           sb.append(s); 
       }
       
       return Long.parseLong(sb.reverse().toString()); //3
   }
}

 

1. 쪼갠 문자열을 오름차순으로 정렬한다.

2. StringBuilder에 붙인다.

3. reverse() 함수를 통해 문자열을 뒤집은 후 반환한다.

 

StringBuilder.reverse()는 문자열을 뒤집을때 사용한다. 오름차순으로 정렬된 문자열을 뒤집어 내림차순과 같게 만드는 것이다.

 

전형적인 선택정렬 알고리즘을 활용해서 풀을 수 있다.

 

import java.util.Arrays;

class Solution{
   public long solution(long n){
       char[] c = String.valueOf(n).toCharArray();
       int temp = 0;
       
       for(int i = 0; i < c.length; i++){
           for(int j = i+1; j < c.length; j++){
               if(c[i] < c[j]){
                   temp = c[i];
                   c[i] = c[j];
                   c[j] = (char)temp;
               }
           }
       }
       
       return Long.parseLong(String.valueOf(c));
   }
}

 

자기 자신 외의 숫자를 비교해서 큰 숫자와 작은 숫자 자리를 바꿔가면서 정렬을 맞추는 알고리즘이다.

 

마지막으로 스트림과 람다식으로 풀어보자.

 

import java.util.Comparator;

class Solution{
   public long solution(long n){
       StringBuilder sb = new StringBuilder();
       String.valueOf(n).chars() //1
           .mapToObj(is -> (char)is) //2
           .sorted(Comparator.reverseOrder()) //3
           .forEach(ch -> sb.append(ch)); 
        
       return Long.parseLong(sb.toString()); //4
   }
}

 

1. chars() 메소드로 String 을 IntStream 으로 가져온다.

2. Int를 Char 형식으로 변환한다.

3. 내림차순 정렬한다.

4. StringBuilder 에 담은 후 Long 타입으로 변환하여 반환한다.

 

 

---

Comparator 인터페이스
Comparator인터페이스는 Java의 java.util 패키지에 속하는 인터페이스로 객체를 담고있는 컬렉션의 전체 객체 순서를 재정렬하기 위한 비교함수이다.
Comparator를 정렬 메서드(Collections.sort 또는 Arrays.sort 등)에 건네 주어, 정렬 순서를 정확하게 제어하고, 비교자를 사용하여 특정 데이터 구조 (정렬 된 Set 클래스 또는 Map 클래스)의 순서를 제어하거나 자연 순서가 없는 객체의 컬렉션을 정렬 할 수 있다.
정렬 대상이 되는 객체에 대한 비교함수의 결과는 항상 동일해야 하며 경우에 따라 비교결과가 다르게 나오는 경우는 범위 규약위반으로 예외(Exception)을 발생시킬 수 있다.
메소드
int compare(Object o1, Object o2)
지정된 두 매개변수를 비교해 첫 번째 인수가 두 번째 인수보다 작으면 음수를 반환하고, 큰 경우는 양수, 동일한 경우는 0을 반환한다.
boolean equals(Object obj)
지정된 매개변수가 해당 Comparator와 동일한 객체인지를 확인해 동일한 경우 true를 반환한다. 동일한 객체의 기준은 두 개의 서로 다른 비교 인수에 대해 각각의 Comparator 객체에서 동일한 결과를 반환하는 경우 동일하다고 판단한다.

-출처 : http://www.incodom.kr/Java/java.util.Comparator

...참고로 기본 정렬조건이 오름차순인 이유는 Class 내에 기본적으로 구현되어있는 Comparable Interface의 compareTo 메서드를 기준으로 하기 때문입니다. Java에서 인스턴스를 서로 비교하는 클래스들은 모두 Comparable 인터페이스가 구현 되어 있습니다.

내림차순이 이나 원하는대로 정렬 조건을 달리 하려면 어떻게 해야할까요? 위에 언급했던 것 처럼 정렬할 Class내에 구현되어 있는 Comparable 인터페이스의 compareTo() 메서드를 원하는 조건으로 오버라이드하거나 익명 인터페이스 java.util.Comparator를 구현한 Class내 compare() 메서드를  원하는 정렬조건으로 오버라이드하여 sort 메서드 호출시 구현한 Comparator 클래스를 명시해 주시면 됩니다.

주의할 점은 byte, char, double, short, long, int, float같은PrimitiveType의 배열에는 적용이 불가능하니 Integer같은 Wrapper "Class"를 이용하셔야 한다는 점입니다.

FunctionalInterface Comparator, java.util.Collections 클래스의 reverseOrder() 메서드는 이미 내림차순으로 구현되어 있는 Comparator를 반환합니다. 만약 내가 원하는 조건으로 정렬조건을 적용하고 싶다면 아래와 같이 Comparator 인터페이스의 compare 메서드를 오버라이드한 Class를 재정의 하여 넘겨 주시면 됩니다.
--------------------------------------------------------------------------------------------------------------------------------
class CustomComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1); //내림차순
    }
}

String[] stringArr = new String[] {"A","C","B","E","D"};
Arrays.sort(stringArr,new CustomComparator()); // stringArr : E D C B A
--------------------------------------------------------------------------------------------------------------------------------
Arrays.sort(stringArr, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1); //내림차순
    }
});

-출처 : https://ifuwanna.tistory.com/232

 

---

[ 문제 출처 : 프로그래머스 ]

 

참고

- https://gogoma.tistory.com/36

- https://velog.io/@stella317/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EB%82%B4%EB%A6%BC%EC%B0%A8%EC%88%9C%EC%9C%BC%EB%A1%9C-%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0 

- https://hogu-programmer.tistory.com/32