[프로그래머스/42746] 가장 큰 수

in Study / Coding Test

☑️ 문제

프로그래머스 42746

☑️ 풀이

첫 번째 시도

  • 미완성 코드이다.
  • 처음 시도한 방법은 10 이상인 배열과 10 미만인 배열 두 개로 나누어서 내림차순으로 정렬 후 각 원소를 비교하는 것이었다.
  • 10 이상인 배열의 원소는 십의 자리를 먼저 잘라 10 미만인 배열의 원소와 비교하여 큰 것을 맨 앞에 두려했다.
  • 하지만 “numbers의 원소는 0 이상 1,000 이하입니다.” **라는 조건에서는 100이상 원소의 배열도 고려해야했는데 이건 좀 비효율적인 것 같아 다른 방법을 생각해보았다.
import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        int startIdx1 = 0;
        int startIdx2 = 0;
        
        Arrays.sort(numbers);
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] >= 10) {
                startIdx2 = i;
            }
        }
    
        // 내림차순 정렬
        int[] arr1 = sort(numbers, 0, startIdx2);            
        int[] arr2 = sort(numbers, startIdx2, numbers.length);
        
        return answer;
    }
    
    public int[] sort(int[] arr, int startIdx, int endIdx) {
        int[] newArr = Arrays.copyOfLength(arr, startIdx, endIdx);
        Arrays.sort(newArr, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b.compareTo(a);
            }
        })
        return newArr;
    }
}

두 번째 시도

  • int[] 인 numbers 를 String[] 로 변경한 후, 두 문자열을 더했을 때의 값을 비교하는 Comparator를 작성하여 배열을 정렬하였다.
    • 예를 들어, a는 3, b는 22인 문자열을 더하는 경우 322, 223이 된다. 여기서 두 수를 비교했을 때 더 큰 값이 앞으로 오게 된다.
  • 이 풀이는 한 가지 테스트 케이스를 통과하지 못하였다.
    • 반례를 찾아보니 입력값 〉 [0, 0, 0], 기댓값 〉 "0" 인 경우를 충족시키지 못하고 있었다.
import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] strNumbers = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
        
        // 두 문자열을 더했을 때의 값을 비교하는 comparator 작성
        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String str1 = a + b;
                String str2 = b + a;
                return str2.compareTo(str1);
            }
        });
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strNumbers.length; i++) {
            sb.append(strNumbers[i]);
        }
        
        return sb.toString();
    }
}

세 번째 시도

  • 정렬된 배열의 첫 번째 문자열의 첫 번째 자리의 값이 0인 경우에만 0을 리턴하도록 했다.
//시간: 205.95ms
//메모리: 132MB

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] strNumbers = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(strNumbers, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String str1 = a + b;
                String str2 = b + a;
                return str2.compareTo(str1);
            }
        });

        if (strNumbers[0].charAt(0) == '0') {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strNumbers.length; i++) {
            sb.append(strNumbers[i]);
        }

        return sb.toString();
    }
}

☑️ 문법 정리 1 - String.valueOf()

  • 다양한 데이터 타입을 문자열로 변환한다.
// 정수를 문자열로 변환
int num = 42;
String strNum = String.valueOf(num);  // "42"

// 실수를 문자열로 변환
double pi = 3.14;
String strPi = String.valueOf(pi);  // "3.14"

// 불리언 값을 문자열로 변환
boolean isTrue = true;
String strTrue = String.valueOf(isTrue);  // "true"

// 문자와 문자 배열을 문자열로 변환
char letter = 'A';
char[] letters = {'H', 'e', 'l', 'l', 'o'};
String strLetter = String.valueOf(letter);  // "A"
String strLetters = String.valueOf(letters);  // "Hello"
  • toString()과 유사하지만, null을 처리하는 방식에서 차이가 있다.
    • String.valueOf()는 null 을 처리 시 null 을 반환한다.
    • toString() 은 null 을 처리 시 NullPointerException 을 반환한다.
Object obj = null;

// String.valueOf()
System.out.println(String.valueOf(obj));  // "null"

// obj.toString()
System.out.println(obj.toString());      // NullPointerException

☑️ 문법 정리 2 - Arrays.sort()

  • 배열을 오름차순(기본값) 또는 사용자 정의 방식으로 정렬하는 데 사용된다.

기본 정렬 (오름차순)

  • int, double, char 와 같은 기본형 배열과 String , Integer 와 같은 객체형 배열 모두 정렬 가능하다.
public class Main {
    public static void main(String[] args) {
        int[] numbers = {5, 3, 8, 1, 2};
        Arrays.sort(numbers);
        System.out.println(Arrays.toString(numbers));  // [1, 2, 3, 5, 8]
    }
}

부분 정렬

  • 배열의 특정 범위만 정렬할 수 있다.
  • 범위는 [startIndex, endIndex] 로 startIndex 포함, endIndex 제외이다.
int[] numbers = {5, 3, 8, 1, 2};
Arrays.sort(numbers, 1, 4);  // 인덱스 1부터 3까지 정렬
System.out.println(Arrays.toString(numbers));  // [5, 1, 3, 8, 2]

객체 배열 정렬

  • Comparator을 사용해 사용자 정의 정렬을 수행할 수 있다.
    • Comparator 는 두 객체를 비교하여 정렬 순서를 정한다.
    • compare(o1, o2)
      • 오름차순은 o1 - o2 , 내림차순은 o2 - o1 로 정렬한다. **
      • 양수 반환 시, o1이 o2보다 뒤로 간다.
      • 음수 반환 시, o1이 o2보다 앞으로 간다.
      • 0 을 반환 시, 순서 변경은 없다.
  • Arrays.sort(array, Comparator<T>);
String[] words = {"apple", "banana", "cherry"};
Arrays.sort(words, new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s2.compareTo(s1); // 내림차순 정렬
    }
});

System.out.println(Arrays.toString(words)); // [cherry, banana, apple]
  • 람다식을 사용해서 정렬 규칙을 간결하게 작성할 수 있다.
String[] words = {"apple", "banana", "cherry"};
Arrays.sort(words, (s1, s2) -> s2.compareTo(s1));
System.out.println(Arrays.toString(words)); // [cherry, banana, apple]

정렬 응용

  • 문자열 길이에 따라 정렬할 수 있다.
String[] words = {"apple", "banana", "kiwi", "cherry"};
Arrays.sort(words, (s1, s2) -> s1.length() - s2.length()); 
System.out.println(Arrays.toString(words));  // [kiwi, apple, banana, cherry]
  • 정수형 숫자를 사전순으로 정렬할 수 있다.
  • compareTo()를 사용하여 문자열을 사전순으로 정렬한다.
Integer[] numbers = {20, 3, 100, 5};
Arrays.sort(numbers, (s1, s2) -> String.valueOf(s1).compareTo(String.valueOf(s2)));
System.out.println(Arrays.toString(numbers));  // [100, 20, 3, 5]

© 2021. All rights reserved.

yaejinkong의 블로그