99클럽 코테 스터디 11일차 TIL + 가장 큰 수(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 정렬

공부한 내용 본인의 언어로 정리하기

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

문제를 간략히 설명하자면, 배열로 주어진 0부터 1000 사이의 숫자들을 활용해 가장 큰 수를 만드는 문제였다.

그래서 정렬을 어떤 방식으로 할 지 열심히 고민해야 하는 문제였다.

 

개인적으로 풀이가 최적의 시간으로 풀었다고는 생각하지는 않았고, 다른 사람들의 풀이도 찾아봤지만

나름 스스로 아이디어를 가지고 풀었기에 작성했다.

 

풀이 과정은 다음과 같다.

1. 두 숫자의 각 자리수마다 비교해서 다르다면 큰 숫자를 return한다.

2. 이 과정을 각 자리수의 곱만큼 반복한다(만약 123과 1234같은 형식이라면 최대 12번 반복한다)

2 - 1. 반복하는 도중 숫자의 자리수가 넘어간다면 원래 숫자의 자리수로 나머지 연산자를 적용하고 비교한다.

(만약 123과 1234를 비교할 때 4번째 자리수를 비교하는 경우 123/1 -> 1과 1234 -> 4를 비교한다)

3. 그래도 전부 동일하다면 이는 우선순위가 동일한 숫자이다.

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    public String solution(int[] numbers) {
        
        int length = numbers.length;
        
        String[] numberStr = new String[length];
        
        for (int i = 0; i < length; i++) {
            numberStr[i] = String.valueOf(numbers[i]);
        }
        
        Arrays.sort(numberStr, (o1, o2) -> {

            char[] str1 = o1.toCharArray();
            int length1 = str1.length;

            char[] str2 = o2.toCharArray();
            int length2 = str2.length;

            int gcd = length1 * length2;

            int i = 0;

            while (i < gcd) {

                char c1, c2;
                c2 = length2 <= i ? str2[i % length2] : str2[i];
                c1 = length1 <= i ? str1[i % length1] : str1[i];
                if (c1 != c2) return c2 - c1;
                i++;
            }
            
            return 0;
        });
        
        StringBuilder sb = new StringBuilder();
        
        if (numberStr[0].equals("0")) return "0";
        for (String number : numberStr) {
            sb.append(number);
        }
        return sb.toString();
    }    
}

 내일 학습할 것은 무엇인지

내일은 코드트리 삼성 기출문제를 풀 예정이다.