Programmers_Sort_2_가장 큰 수 (Java)

문제 풀이에 대한 오류 지적 및 개선 방향 제시는 항상 환영합니다.
알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서
그 어떤 문제에 대한 비판 지적 방향제시는 언제나 감사하게 받겠습니다. 

이 문제가 올라가는 저장소 : https://github.com/hwk0911/Junit-TDD

hwk0911/Junit-TDD

문제 설명

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

 

<풀이>

문제 해결에 너무 많은시간이 걸렸다. 보고 아 문자열 내림차순 정렬이구나! 하고
Junit Test 돌려보니, 2번 테스트에서 에러가 났다.

"9534330" 이 아닌 "9534303"이 나와 생긴 에러다. 곰곰히 생각해보니 당연한 결과다.

Java에서 제공하는 사전식 정렬의 내림차순으로 정렬을 해 보면,
9, 5, 34, 30, 3 순으로 나오는데, 그냥 머릿속으로 생각만 해도 30과 3의 자리는 바뀌어야 한다.

그래서 compareTo 함수를 사용하여, 두 문자열을 합친 경우를 기준으로 내림차순 정렬하여 해결했다.

Solution.java

import java.util.*;

public class Programmers_Sort_2 {
    public String solution(int[] numbers) {
        ArrayList<String> strList = new ArrayList<>();

        for(Integer index : numbers){
            strList.add(index.toString());
        }

        Collections.sort(strList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        //Collections.sort To lambda
        //Collections.sort(strList, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

        if(strList.get(0).startsWith("0")){
            return "0";
        }

        Iterator<String> strItr = strList.iterator();
        String answer = "";

        while(strItr.hasNext()){
            answer += strItr.next();
        }

        return answer;
    }
}

IntelliJ 로 넘어와 신세계를 봤다. Collections.sort 함수를 자동으로 lambda로 바꿔주는 기능이 있었다!

람다는 천천히 공부할 생각이라, 우선은 주석처리만 했다. ㅎㅎ

코드 분석

1. ArrayList<String>을 선언하여, 매개변수인 int[] numbers의 모든 원소를 String으로 변환하여 저장한다.
2. compareTo 함수를 오버라이드 하여 두 문자열을 합친 기준으로 내림차순 정렬한다.
3. 정렬 된 ArrayList의 첫 원소가 0으로 시작하는 경우 생성 가능한 최대 수는 0이다.
   예외처리 없이 {"000", "0000", "00000"}를 실행 한 결과는 "000000000000"가 된다. (함정)
4. 검색을 위해 Iterator<String>을 선언한다.
5. answer += iterator.next() 를 통해 가장 큰 수를 만든다.
6. return answer;

SolutionTest.java

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

class Programmers_Sort_2Test {

    @Test
    void solution() {
        Programmers_Sort_2 ps2 = new Programmers_Sort_2();

        int numbers[] = {6, 10, 2};
        String answer = "6210";

        assertEquals(answer, ps2.solution(numbers).intern());

        int numbers_2[] = {3,30,34,5,9};
        answer = "9534330";

        assertEquals(answer, ps2.solution(numbers_2).intern());

        int numbers_3[] = {0,000,0000,0000000,0000000};
        answer = "0";

        assertEquals(answer, ps2.solution(numbers_3).intern());
    }
}

단위테스트를 위한 Junit 테스트 클래스다.

테스트 케이스에 대한 항목 2개와, 예외처리{0,000,0000,0000000,0000000}에 대한 테스트를 진행한다.

+ ps2.solution의 결과는 String Constant Pool에 저장되지 않고, Heap에 저장되므로,
intern() 함수를 통해 처리했다.