[알고리즘 문제풀이] 프로그래머스 가장 큰 수

2021년 첫 알고리즘 문제풀이 ! 열심히 달려보자 ! 🔥

2020년 하반기부터 프로그래머스 코딩테스트 연습 고득점 kit 문제 풀이를 시작했다 ! 30-35 문제밖에 안되는 것 같은데 아직도 다 못 풀었다니 얼마나 게을렀는지 알 수 있는 부분..

먼저 문제의 링크는 아래와 같다 !
https://programmers.co.kr/learn/courses/30/lessons/42746

문제 설명

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

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

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

제한 사항

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

입출력 예시

시행착오 ( 그저 회고/기록 목적으로 풀이를 원하시면 아래로 ! 😉 )

사실 거의 3-4일을 질질 끌며 문제를 풀어서 이런 저런 시행착오를 거쳤지만 기억이 잘 나지 않는다..

먼저 이 문제는 레벨2로 분류되어 있는데, 다른 레벨2 문제에 비해서 고민과 시행착오를 많이 거쳤던 거 같다.

입출력 예시만 보고 입력 원소들을 모두 String으로 바꾸어 저장하고, 정렬하면 된다는 생각을 가졌다. ( 사실 결과적으로 풀이 방법도 이와 별 다를 건 없다. ) 하지만 [12, 121] 의 예시 반례를 발견하게 되었고, 12가 공통된 문자열이기 때문에 startwith를 이용해서 공통된 문자열로 시작되는지를 판별하고 12뒤에 오게될 가능성이 있는 121과 112를 비교하는 방법을 택했다. 하지만 그 알고리즘을 구현하는 과정에서도 문제가 생겼다 !

한참 반례를 못 찾다가 다음과 같은 반례를 포함하고 다양한 경우를 테스트 해볼 테스트 케이스를 만들었다.

[3, 30, 34, 4, 40, 42, 421, 423, 45]

직접 위의 테스트 케이스의 결과를 만들어보고 들여다보니 사전식 정렬을 하면 되겠다는 생각이 들었다 ! 그래서 사전식 정렬을 고민하며 이런 저런 알고리즘들을 찾아보다가 단순 compare override로 구현하면 되겠다는 힌트를 얻게 되었다 !

풀이 방법

그래서 결과적으로 어떻게 문제를 풀었냐 ! 너무 뺑뺑 돌아왔지만 결국은 정렬에 분류되어있는 문제답게 정렬로 문제를 해결했다.

람다식을 이용하여 sort의 compare를 두 문자열을 더했을 때 더 큰 순서로 정렬되게끔 코드를 작성하여 간단하게 문제가 풀렸다 !

문제를 풀고나니 처음 문제 접근을 잘못했고, 그 코드를 보존하고 예외를 잡아가다 보니 얼마나 복잡하고 무의미한 시간들을 보냈는지 알 수 있었다. 그리고 왜 레벨2이고, 정렬에 분류되어 있는지도 명확하게 깨달을 수 있었다

코드

/*
 * 2020.01.06
 * gowoon-choi/github.com
 * programmers 가장 큰 수
 */

package com.gowoon;

import java.util.*;

public class Solution {
    static public String solution(int[] numbers) {
        String result = "";
        ArrayList<String> convertedArr = new ArrayList<>();
        for (int number : numbers) {
            convertedArr.add(String.valueOf(number));
        }
        convertedArr.sort((num1, num2)-> (num1+num2).compareTo(num2+num1));
        for (String s : convertedArr) {
            result = s + result;
        }
        while (result.length() > 1 && result.charAt(0) == '0'){
            result = result.substring(1);
        }
        return result;
    }
}