본문 바로가기

알고리즘 문제풀이/프로그래머스

[프로그래머스] 가장 큰 수 with JAVA

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

 

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

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰

programmers.co.kr

문제 설명

 

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

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

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

class Solution {
    public String solution(int[] numbers) {
        int size = numbers.length;
        Integer[] wr_numbers = new Integer[size];
        for (int i = 0; i < size; i++){
            wr_numbers[i] = numbers[i];
        }
        Arrays.sort(wr_numbers, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                String s1 = Integer.toString(o1);
                String s2 = Integer.toString(o2);
                int start_o1 = Integer.parseInt(s1 + s2);
                int start_s2 = Integer.parseInt(s2 + s1);
                if (start_o1 > start_s2) return -1;
                else if (start_o1 < start_s2) return 1;
                else return 0;
            }
        });
        if (wr_numbers[0] == 0) return "0";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++){
            sb.append(wr_numbers[i]);
        }
        String answer = sb.toString();
        return sb.toString();
    }
}

1. 어려웠던 점:

- 테스트 케이스 한 개가 계속 오류가 생겨, 애를 먹었다. 000, 00 등의 경우가 올 때를 생각하지 못해서 였다.

 

2. 알게된 점:

- 정렬 문제 복습 (Comparator, compare 활용을 헷갈리지 말고 잘하자.)

 

3. 알고리즘 풀이:

- 먼저, Arrays.sort에서 comparator를 사용하기 위해, Int배열을 wrapper class인 Integer배열로 변경하였다.

그 후, 숫자 A와 B를 비교할 때, string으로 A+B했을 때와, B+A를 비교해

A+B가 더 크면 A가 먼저와야 하므로 -1

B+A가 더 크면 B가 먼저와야 하므로 1을 반환하도록 compare함수를 Override하였다.

 

- 결과값이 000이든 00이든 0을 반환해야 하기 때문에 첫 번째 글자가 0인지 확인한 후, 0이면 "0"을 반환

나머지는 정렬된 배열의 순서대로 문자열을 만들어 반환하면 된다.