가장 큰 수 - 프로그래머스 42746

문제 링크

코딩테스트 연습 - 가장 큰 수 | 프로그래머스 (programmers.co.kr)

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

 

문제 설명

 

매개변수로 숫자들이 주어졌을 때, 숫자들을 재배치해 가능한 숫자들 중에서 가장 큰수를 문자열로 return 하면 된다.

문자열로 리턴하는 이유는 값이 너무 큰 경우도 있기 때문이다.

 

제한 사항

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

 

관건은 자리수가 다른 숫자들을 어떻게 배치하느냐 이다.

 

 

풀이

1)

위 예시처럼 numbers: [6,10,2] 인 경우 맨 앞 자리만을 비교해서 정렬하면 된다.

6> 2> 1 이므로 6 10 2 순으로 배치하면 될 것이다.

 

문제는 3, 30 34 인 경우이다. 이 경우에는 첫번째 수가 3으로 같으므로, 다음자리 숫자를 비교해 볼 수 있다. 하지만 3의 경우는 어떻게 해야할까?

3 -> 33 으로 바꾸어보면 두 번째 자리는 0, 3, 4가 되고,

4 >3 > 0 이므로 34, 3 , 30 순으로 배치하면 된다.

 

1. 숫자의 자리수가 일치할 경우 : 첫번째 자리부터 끝자리까지 순차적으로 수를 비교해가며 정렬

2. 숫자의 자리수가 다를 경우: 자리수가 짧은 숫자뒤에 앞자리 수를 덧붙여서 비교한다.

 

하지만 위의 풀이는 코드를 짜보면 복잡하다는 것을 알게 된다.

 

 

2)

1) 번처럼 생각하지 말고, 정렬을 두 문자열을 순서를 바꿔 합친 후에, 그 값을 비교해보는 것이다.

Comparator를 사용하여 문자열을 붙인 뒤 내림차순으로 정렬해야 한다.

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

 

x.compareTo(y) 로 String 값 비교

: x - y 순서로 아스키코드 값을 뺀 결과를 리턴한다.

• x > y  : return 값 > 0
• x = y  : return 값 = 0
• x < y  : return 값 < 0

내림차순 정렬 : (o2+o1).compareTo(o1+o2);

오름차순 정렬 : (o1+o2).compareTo(o2+o1);

 

 

또 숫자가 0인 경우는 무조건 뒤에 배치하므로, numbers 에 0 이 들어있는 갯수만큼 나중에 따로 빼서 뒤에 더해준다.

이 개수만큼 빼서 sort 를 진행하기 때문에 시간이 단축된다.

 

 

 

예외처리

numbers[]에 숫자들이 전부 0만 있을 경우 답이 "00000..." 이 되므로 이 경우에는 따로 예외처리를 해줘야 한다. : "0" 리턴

 

 

소스코드

public String solution(int[] numbers) {
    String answer = "";
    int numOfZero = 0;

    List<String> list = new ArrayList<>();
    for (int n : numbers) {
        if(n!=0) list.add(Integer.toString(n));
        numOfZero++;
    }

    if(numOfZero == numbers.length) return "0";

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

    for (String s : list)
        answer+=s;

    for(int i=0;i<numOfZero;i++)
        answer+="0";

    return answer;
}