[프로그래머스]정렬 : 가장 큰 수 (level 2) (java, c++)

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수 | 프로그래머스

 

java 코드

import java.util.Arrays;
import java.util.Comparator;
 
class Solution {
 
    public String solution(int[] numbers) {
        
        // int배열 -> String배열
        String[] arrStrNumbers = new String[numbers.length];
 
        for (int i = 0; i < numbers.length; i++) {
            arrStrNumbers[i] = numbers[i]+"";
        }
        
        // 문제에 주어진 기준대로 정렬
        Arrays.sort(arrStrNumbers, new Comparator<String>() {
            
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });
        
        // 0이 가장 큰 수인 경우, 0만 리턴 (000 과 같은 중복 제거)
        if(arrStrNumbers[0].startsWith("0")) {
            return "0";
        }
        
        // String배열 -> String
        StringBuilder sbAnswer = new StringBuilder();
 
        for (int i = 0; i < arrStrNumbers.length; i++) {
            sbAnswer.append(arrStrNumbers[i]);
        }
        
        return sbAnswer.toString();
    }
}

 

c++ 코드

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int compare(const string& a, const string& b)
{
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
 
    // 숫자 벡터 -> 문자열 벡터
    vector<string> str_nums(numbers.size());
    for (int i = 0; i < numbers.size(); i++)
    {
        str_nums[i] = to_string(numbers[i]);
    }
 
    // 두 수를 이어붙였을 때를 가정하여 내림차순으로 정렬
    sort(str_nums.begin(), str_nums.end(), compare);
 
    // 모두 0일때 예외처리
    if (*str_nums.begin() == "0")
    {
        return "0";
    }
 
    // 모두 이어붙이기
    string answer = "";
    for (auto iter = str_nums.begin(); iter < str_nums.end(); iter++)
    {
        answer.append(*iter);
    }
    return answer;
}

 

 

순서를 재배치하여 만들 수 있는 가장 큰 수

를 구하는 게 문제의 목적이었다. 

 

[9, 30, 34, 5, 3]을 문제에서 요구하는대로 정렬하면 [9, 5, 34, 3, 30]이지만

이는 오름차순도, 내림차순도 아니다. 

숫자를 앞 뒤로 이어 붙였을 때 가장 큰 수가 되어야 하기 때문이다.

 

 

재귀 함수도 구현해보고 이것저것 끙끙 앓았지만, 결국 스스로 해결하지 못해

다른 분들의 풀이 방법을 찾으니 크게 2가지로 나뉘었다. 

 

1. 배열의 원소가 1,000 이하이므로, 각 원소 뒤에 0 패딩을 충분히 붙여줘서 비교한다. 

2. A+B 와 B+A를 비교한다. 

 

 

2번처럼 생각해서 문제와 예시 테스트 결과를 이해했으면서, 어째서 2번을 구현할 생각을 못했을까!

2번 방법은 Comparator을 이용한다. 

Comparable : 기본 정렬 기준 메서드인 Comparable 인터페이스를 구현한다. 익명 클래스로 구현.

Comparator : Comparable은 이미 구현되어 있는 클래스들과 다른 기준을 쓰고 싶을 때 사용

 

 

Arrays.sort( 배열, new Comparator )를 입력하고 unImplemented method를 자동 생성해주면,

다음과 같이 오버라이드 된 compare 메서드가 등장한다.  

이 메서드를 어떻게 구현하느냐에 따라 기준이 달라진다. 

Arrays.sort(arrStrNumbers, new Comparator<String>() {
  
  @Override
  public int compare(String A, String B) {
    return 0;
  }
});

 

원래 compare메서드의 작동원리는 다음과 같다. 

A < B	return 음수
A == B	return 0
A > B	return 양수

 

Arrays.sort()의 기본 구현은 오름차순 이므로, compare 메서드에서

음수 또는 0이 리턴되면 A와 B의 순서는 그대로 유지되고

양수가 리턴되면 A 와 B의 순서가 서로 바뀌게 된다. 

 

 

 

그러면 compare를 가지고 이것저것을 해보자. 

 

1. 기본형. [9, 30, 34, 5, 3] 선언된 배열 순서 그대로 출력된다. 

Arrays.sort(arrStrNumbers, new Comparator<String>() {
  
  @Override
  public int compare(String o1, String o2) {
    return 0;
  }
});
-------------------------------------------------------------------
9
30
34
5
3

 

2. 오름차순

Arrays.sort(temp, new Comparator<String>() {
 
  @Override
  public int compare(String o1, String o2) {
    return o1.compareTo(o2);
  }
});
-------------------------------------------------------------------
3
30
34
5
9

 

4. 문제의 풀이! A+B 와 B+A 비교해서 내림차순으로 나타내기

Arrays.sort(temp, new Comparator<String>() {
  
  @Override
  public int compare(String o1, String o2) {
    return (o2+o1).compareTo(o1+o2);
  }
});
-------------------------------------------------------------------
9
5
34
3
30

 

 

 

정렬 구현의 신세계를 엿본 느낌이다 ㅎㅎ

새로운 걸 배웠다. 좋은 문제였다.