[프로그래머스] (Java) 가장 큰 수 문제 풀이 (정렬) - compareTo() 메서드

 

1. 문제설명

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

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
 
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
 

제한 사항

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

입출력 예

 

---

2. 접근방식

 
처음에는 Arrays.sort()로 배열을 오름차순 정렬 후,
배열 각 요소들을 String으로 형변환한뒤,
배열 맨 뒤에서부터 꺼내와서 붙이는 방법을 생각 해 봤다. 
 
하지만 여기서 걸리는 점이 10, 100, 1000처럼 앞자리가 1로 시작하는 숫자는 
실제 숫자의 밸류값은 크지만, 사실 숫자를 붙일 때는 1과 똑같이 우선순위가 낮다는 것이다.
이걸 어떻게 처리 해 줘야 할지 고민스러워서... 
 
1+110 = 1110
110+1 = 1101
이것만 봐도 앞자리가 1로 시작하는 숫자들은 1뒤에 붙어야 한다는 걸 알 수 있다.
 
1+120 = 1120
120+1 = 1201
근데 1뒤에 오는 숫자가 1보다 큰 숫자인 경우, 가령 2라면
이번에는 120이 1보다 먼저 와야 된다.
이것때문에 코드를 썼다 지웠다 하면서 고생을 좀 했다. 
머리가 아프다 벌써 ㅎㅎㅎㅎ
그럼 어떻게 해야 하는가... ?
 
결국 단순히 숫자를 오름차순이나 내림차순으로 정렬해서는 결과값이 도출되지 않기 때문에
여기서 써먹을 수 있는 메서드를 찾아 보았다.

---

Comparable 인터페이스에서 제공하는

compareTo() 메서드를 쓰면
문자열을 아스키코드 값으로 비교해서 정렬해 준다. 

Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

 

 

 

• arr: 정렬할 배열,이 배열의 요소는 String 타입이어야 함(compareTo가 문자열 비교 메서드이기 때문)
• (o1, o2): 두 요소를 비교하는 람다 표현식, 여기서 o1과 o2는 배열의 요소
• (o2 + o1).compareTo(o1 + o2): 이 부분이 정렬의 기준
  • 두 요소 o1과 o2를 서로 이어 붙여서 두 개의 문자열을 생성
    • o2 + o1: o2가 먼저 오는 경우의 문자열
    • o1 + o2: o1이 먼저 오는 경우의 문자열
  • 그 다음, compareTo() 메서드를 사용하여 두 개의 문자열을 비교
  • 결과적으로 o2가 o1보다 앞서야 정렬 순서가 유지되므로 내림차순으로 정렬됨

 

이 메서드는 아래와 같이 사용할 수 있는데, 특히 결과를 합칠 때는 StringBuilder를 써서 append() 하는 것이 추천된다.

합치는 연산이 많을 수록 속도면에서 StringBuilder을 쓰는 것이 그냥 += 연산자보다 유리하다. 

 

 

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] arr = {"3", "30", "34", "5", "9"};

        // 내림차순 정렬
        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

        // 정렬된 배열 출력
        System.out.println(Arrays.toString(arr)); // ["9", "5", "34", "3", "30"]
        
        // 결과를 합쳐서 하나의 큰 숫자로 만들기
        StringBuilder result = new StringBuilder();
        for (String str : arr) {
            result.append(str);
        }

        System.out.println(result.toString()); // "9534330"
    }
}

 
만약 오름차순으로 정렬하고 싶으면 (o1 + o2)가 (o2 + o1) 보다 먼저 온다.

// 오름차순 정렬
Arrays.sort(arr, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));

 

---

3. 문제풀이

 

import java.util.Arrays;

public class Solution {
    public String solution(int[] numbers) {
    	// String 타입의 arr 배열 선언
        String[] arr = new String[numbers.length];
		
        // 기존의 int형 배열인 numbers를 순회하면서 값들을 String으로 변환 후
        // arr에 대입
        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }
	
    	// 문자열을 비교하면서 정렬(문자의 아스키 코드로 정렬하는 원리)
        // 인접한 두 개의 문자를 더해서 큰 것이 먼저 오게 한다
        // = 내림차순 정렬
        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        // 모든 값이 0일 경우 0만 리턴
        if (arr[0].equals("0")) {
           return "0";
        }
	
    	// 문자열을 결합 해 주기 위해서 StringBuilder 객체 선언
        StringBuilder answer = new StringBuilder();
		
        for (int i = 0; i < arr.length; i++) {
            answer.append(arr[i]);
        }


        return answer.toString();
    }
}

 
 
여기서 아래 조건문 추가해 주는 이유

if (arr[0].equals("0")) {
   return "0";
}

 
만약 arr[0].equals("0") 조건문이 없다면, 잘못된 결과가 출력된다. 
만약 입력 배열 numbers가 모두 0으로 이루어진 경우 (예: [0, 0, 0]), 
Arrays.sort()를 통해 정렬한 후에도 결과는 ["0", "0", "0"]이다.
 
이 상태에서 StringBuilder를 사용해 모든 요소를 합치면
최종 결과는 "000"이 된다.
하지만 우리가 원하는 값은 그냥 0이지 000이 아니다.
000은 이는 자연수 표현으로 적합하지가 않기 때문에
일반적으로 "0"이라는 단일 숫자를 원하기 때문에 해당 처리를 해 준다. 
 
여기서 이해 안되시는 분들은 다시 한 번 설명드리면
자, arr[0]번 인덱스의 값이 0이면, 해당 프로그램에서 0을 리턴하고
그 뒤 연산은 수행하지 않고 그대로 종료된다는 것인데
현재 정렬은 내림차순이 되어 있기 때문에
첫번째 인덱스 값이 0이면 두 번째, 세번째 도 0인 것이죠....
 
 
 

오답정리

 

---

4. 같은 유형 문제(정렬)

https://awesomepossum.tistory.com/291

[프로그래머스] (Java) K번째수 문제 풀이 (정렬)