[프로그래머스 / Level2] 가장 큰 수 (Java)

문제

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

코딩테스트 연습 - 가장 큰 수

 

풀이 과정

1. int 배열을 String 배열로 변환

최종 결과 문자열이 숫자 그 자체를 더한 문자열이기 때문에, 연산을 위해 int 배열(=numbers)의 모든 요소를 하나씩 String 타입으로 변환시켜 String 배열에 담아준다.

int타입은 기본타입(Primitive Type)이기 때문에 int값에서 바로 toString() 메서드를 할 수는 없고 String.valueOf(int a) 메서드로 int타입 값을 가지는 String객체를 생성해주거나, Integer.toString(int a) 메서드로 int타입을 String타입으로 변경해주는 방법을 이용해야 한다.

String[] strNumbers = new String[numbers.length];

for (int i = 0; i < numbers.length; i++) {
    strNumbers[i] = String.valueOf(numbers[i]);
    // strNumbers[i] = Integer.toString(numbers[i]);
}

 

위 코드를 아래와 같이 작성할 수도 있다.

String str = Arrays.toString(numbers);					// "[6, 10, 2]"
String[] numberStr = str.substring(1, str.length()-1).split(", ");	// "6, 10, 2" -> {6, 10, 2}

 

2. String[] 요소 비교 Comparator 생성

Arrays.sort() 메서드를 통해 1차원 배열을 정렬할 수 있다. 이 때 첫번째 매개변수는 '정렬할 배열' 객체이고, 두번째 매개변수는 '배열 요소를 비교할 기준을 지정해둔 Comparator'이다.

public class Arrays{
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }
}

 

문제에서 구하고자 하는 값은 일반적인 오름차순/내림차순 정렬 결과가 아니기 때문에 사용자가 직접 Comparator 를 생성하고 compare() 메서드를 오버라이드해야 한다.

처음에는 1.첫자리가 큰 값  2.길이가 짧은 값  3.둘째자리가 큰 값  4.셋째자리가 큰 값 의 우선 순위로 정렬하면 원하는 값을 얻을 수 있을 거라 생각하고 아래와 같이 코드를 짰는데 (numbers 요소 값의 범위가 0~1000 이기 때문에 셋째자리까지만 비교)

Arrays.sort(strNumbers, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        // 우선순위 : 1.첫자리 큰 것  2.길이 짧은 것  3.둘째 자리가 큰 것  4.셋째자리가 큰 것
        char c1 = o1.charAt(0);
        char c2 = o2.charAt(0);
        if (c1 != c2) {
            return c2 - c1;                         // 첫자리 내림차순
        }else {
            if (o1.length() != o2.length()) {
                return o1.length() - o2.length();   // 길이 오름차순
            }else {
                if (o1.charAt(1) != o2.charAt(1)) {
                    return o2.charAt(1) - o1.charAt(1);     // 둘째자리 내림차순
                } else {
                    return o2.charAt(2) - o1.charAt(2);     // 셋째자리 내림차순
                }
            }
        }
    }
});

 

다른 경우에는 기대한 대로 결과가 나오나, 세 번째 테스트케이스에서 3, 34, 30 을 비교하는 과정에서 정렬이 잘못되는 걸 볼 수 있다. 

입력	기대 결과	실제 결과	정답 여부
[6, 10, 2]	"6210"	"6210"	O
[9, 98, 90]	"99890"	"99890"	O
[3, 30, 34, 5, 9]	"9534330"	"9533430"	X

 

해당 테스트케이스를 충족하기 위해 문자열의 각 자리수끼리 비교하는 기존의 방식에서, 문자열 자체로 중간 결과를 산출해 비교하는 방식으로 수정하였다. 두 문자열을 더하는 경우 중 (1. A+B,  2. B+A) 더 큰 값을 우선순위로 내림차순 정렬한다.
(ex : 두 비교 대상이 o1, o2가 각각 3, 34일 경우 34+3=343, 3+34=334 두 값을 비교한 결과 343이 더 크기 때문에, 34 → 3 순으로 정렬되게 된다.)

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

 

[람다식 버전]

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

 

[compare() 메서드 처리로직 확인용]

• o2+o1 조합이 o1+o2 조합 보다 크면 양수 => o2가 o1보다 좌측에 옴
• o1+o2 조합이 o2+o1 조합 보다 크면 음수 => o1이 o2보다 좌측에 옴

Arrays.sort(strNumbers, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        int result = (o2 + o1).compareTo(o1 + o2);
        System.out.println(o1 + "과 " + o2 + " 비교 결과 : " + result);
        return result;
    }
});

• 9 > 5 > 34 > 3 > 30

[3, 30, 34, 5, 9]
30과 3 비교 결과 : 3		// 3 -> 30
34과 30 비교 결과 : -4		// 34 -> 30
34과 30 비교 결과 : -4		// 34 -> 30
34과 3 비교 결과 : -1		// 34 -> 3
5과 3 비교 결과 : -2		// 5 -> 3
5과 34 비교 결과 : -2		// 5 -> 34
9과 3 비교 결과 : -6		// 9 -> 3
9과 34 비교 결과 : -6		// 9 -> 34
9과 5 비교 결과 : -4		// 9 -> 5
9534330

 

3. 정렬 순서를 유지한 채 String[] 요소를 하나의 문자열로 합치기

String.join() 메서드를 사용해 구분자를 기준으로 String[] 배열을 하나의 문자열로 연결해준다. 여기서 구분자로 ""을 입력했기 때문에 결과 문자열은 별도의 구분자없이 연속으로 요소가 연결된다.
(ex : String.join("", {1, 2, 3, 4}) => "1234")

return String.join("", strNumbers);

 

만약 입력값이 {0, 0, 0, 0} 과 같이 0만 존재할 경우, 리턴 값이 "0000"이 아니라 "0" 이 되어야 한다.
이를 위해 최종 정렬된 배열의 첫번째 요소가 0일 경우는 "0"을 반환하도록 별도 지정해준다.

if(strNumbers[0].equals("0")) return "0";

 

String[]을 String으로 합칠 때, StringBuffer 객체를 생성한 뒤, String[] 배열의 모든 요소를 append() 해줘도 된다. 마지막 리턴 값이 String타입이어야 하기 때문에 toString() 메서드로 StringBuffer타입을 String타입으로 변환해서 리턴해줘야 한다.

StringBuffer sb = new StringBuffer();

for (String number : strNumbers) {
    sb.append(number);
}

return sb.toString();

 

코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String solution(int[] numbers) {
        String[] strNumbers = new String[numbers.length];

        // int[] -> String[] 변환
        for (int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }

        // String[] 배열 정렬
        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        if(strNumbers[0].equals("0")) return "0";
        
        return String.join("", strNumbers);
    }
}

 

★ 정렬(Sorting) 문제 풀이법

배열을 입력값으로 주고 일정한 기준으로 정렬하는 문제이기 때문에, 대부분 Arrays.sort() 메서드에 사용될 Comparator - compare() 메서드를 적절히 작성하는 것이 관건이다. if문, compareTo() 메서드를 통해 값들의 정렬 기준을 지정해준다. 이때 비교 대상은 정수(Integer), 문자열(String), 사용자 정의 타입(객체) 등 다양할 수 있다.