가장 큰수 -프로그래머스 정렬 문제-

문제 설명

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

python 풀이 

---

첫 번째 풀이(실패)

def solution(numbers):
    answer = ''
    numbers = list(map(str,numbers))
    numbers.sort(reverse=True)
    answer = "".join(numbers)
    return answer

numbers를 str로 바꿔준 후 sort로 정렬해주었다 int일 때 비교 안 하고 str로 바꿔준 후 비교한 이유로는

10과 6을 비교할때 int는 10이 크다고 하지만 str은 6이 크다고 판단한다 그렇기 때문에 6,10,2에서

6이 가장 크고 2 10 순으로 정렬 되어야만 6210이 나오기 때문에 str로 바꿔준 후 비교하였다

높은 숫자가 나올것이라고 생각했지만 30,34,3 같은 경우 34,3,30이 아닌 34,30,3으로 정렬해서 결과가 다르게 나왔다

 

두 번째 풀이(실패)

def solution(numbers):
    answer = ''
    numbers = list(map(str,numbers))
    numbers.sort(key = lambda x:x*3 ,reverse=True)
    answer = "".join(numbers)
    return answer

위 방법이 잘못돼서 다시 문제를 보니 numbers의 원소는 1000 이하라고 했기 때문에 3자리 숫자이다 

따라서 lambda를 통해서 만약 3인 경우 333 34인 경우 343434로 만들어서 비교하였다 그렇게 하니 

올바른 결과가 나왔으나 34,3,30을 비교했을때 올바른 결과가 나와서 이렇게  문제를 풀었다

하지만 11번 테스트 게이스에서 실패가 나왔다

 

마지막 풀이(성공)

def solution(numbers):
    answer = ''
    numbers = list(map(str,numbers))
    numbers.sort(key = lambda x:x*3 ,reverse=True)
    if sum(list(map(int,numbers))) == 0:
        answer = '0'
    else:
        answer = "".join(numbers)
    return answer

 

11번의 테스트 케이스의 경우를 생각해보니 [0,0,0]같은 경우 0이 나와야 하는데

두 번째 풀이 처럼하면 0이 아닌 000이 나오게 된다

따라서 이 경우를 0으로 처리하기 위해서 전부 더했을 때 0인 경우 answer를 0으로 나오게 해 주었다

 

java 풀이

---

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        Map<String, String> map = new HashMap<>();
        ArrayList numberlist = new ArrayList();
        ArrayList answerlist = new ArrayList();
        int sum = 0;
        for(int i =0; i<numbers.length; i++){
            sum = sum + numbers[i];
            String str =  Integer.toString(numbers[i]);
            map.put((str+str+str),str);
            numberlist.add((str+str+str));
        }
        Collections.sort(numberlist);
        for(int i=numberlist.size()-1; i >= 0; i--){
            answerlist.add(map.get(numberlist.get(i)));
        }
        if(sum ==0){
            answer = "0";
        }
        else{
            answer = String.join("",answerlist);
        }
        return answer;
    }
}

 

python과 같은 방식으로 풀었습니다

hashmap을 만들어서 x*3을 str+str+str로 key로 저장하였고 value로 str을 저장하여 원래 숫자를 알 수 있게 하였습니다

str+str+str을 numberlist에 넣어서 sort를 통해 누가 더 높은 숫자인지 판별할 수 있게 하였고

sum을 통해서 [0,0,0] 같은 경우에 0이 나올 수 있게 하였습니다

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges