[코테/JAVA] 정렬 : 가장 큰 수

2022.03.20

88번째 포스팅

 

입사 378일차.

코테 문제풀이 17주차 1번 문제

 

 

0. 문제

  ① 정렬 : 가장 큰 수

  ② 설명

문제설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

  ③ 링크

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

 

 

1. 접근방법

  생각해낸 방법은 2가지

  ① 자릿수를 변환해서 비교 (HashMap)

  ② 자릿수를 변환해서 비교 (구조체)

 

 

2. 풀이

  ① 접근방법 : ①

  ② 풀이

import java.util.*;
import java.util.Map;
import java.util.Map.Entry;
 
class Solution {
    /*
     * Date: 2022-03-20
     * Time: 21:12
     */
    public String solution(int[] numbers) {
        String answer = makeDigit(numbers);
        return answer;
    }
    
    /*
     * 메소드명: 자릿수만들기
     * 1. numbers의 원소는 최대 4자리까지 가능
     * 2. 배열안의 모든 값을 4자리로 변환
     * 3. HashMap의 Key에는 원래값, Value에는 자릿수를 변환한 값을 put
     */
    public String makeDigit(int[] numbers) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int tmpNum = numbers[i];
            String parsingNum = Integer.toString(numbers[i]);
            
            while(parsingNum.length() < 4) {
                parsingNum += parsingNum;
            }
            
            map.put(tmpNum, Integer.parseInt(parsingNum.substring(0, 4)));
        }
        
        return madeMaxNum(map);
    }
    
    /*
     * 메소드명: 최댓값만들기
     * 1. compare메소드를 override하여 Value값에 따라 HashMap을 내림차순정렬
     * 2. 내림차순정렬된 HashMap의 Key들을 Sum
     */
    public String madeMaxNum(Map<Integer, Integer> map) {
        List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
        Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
            public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        
        String answer = "";
        for (Entry<Integer, Integer> entry : list) {
            answer += entry.getKey();
        }
        
        return answer;
    }
}

 

 

3. 결과

 

 

4. 주의사항

  ① HashMap을 사용하면서 배열의 모든 값들이 '0'일때에 대한 예외처리는 했으나, 중복된 key를 넣지 못해 1 ~ 7번까지의 테스트케이스에서 모두 실패했다.

  ② 자릿수를 비교하려면 구조체를 사용하거나 List안에 다시 List를 넣어서 처리해야할 것 같다.