[ᴘʀᴏɢʀᴀᴍᴍᴇʀꜱ] 정렬 - 가장 큰 수

NewHa·2023년 9월 12일

algorithm programmers

ᴘʀᴏɢʀᴀᴍᴍᴇʀꜱ

목록 보기

1/8

🧩 가장 큰 수

🎯 문제 설명

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

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

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

🥅 제한 사항

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

🙆🏻‍♀️ 문제 풀이

우선 숫자의 앞자리를 기준으로 정렬을 해야한다고 생각했다. 숫자에는 index가 없으므로 numbers의 요소들을 문자열로 바꿔준 후 [0]번 index를 기준으로 정렬을 해줬다.

function solution(numbers) {
  numbers = numbers.map(el => String(el)).sort((a, b) => b[0] - a[0]);
  console.log(nubmers); // [ '9', '5', '3', '30', '34' ]
}

정렬을 하고 나니 ['3', '30', '34'] 처럼 [0]번 index의 숫자가 같은 경우 문제가 되었다. 문자정렬이므로 자리수가 가장 적은 '3'이 가장 순서가 앞으로 나왔다. 숫자로 정렬을 해서 [34, 30, 3]이 되어도 안되었다. 왜냐하면 34303 보다 34330이 더 크므로 [34, 3, 30] 순으로 정렬이 되어야 했다.

이전에 공부한 기수 정렬이 떠올라서 뒤에 0을 붙여 정렬을 해보았으나 [340, 300, 300]으로 소용이 없었다.

구글링을 통해 수를 반복해서 늘려서 비교하는 방법을 찾았다. (이런 생각은 대체 어떻게 하는 걸까?)
[3333, 3434, 3030]으로 만들어서 정렬하면 [3434, 3333, 3030]으로 정렬이 된다.

하지만 이렇게 순서를 맞춰놓고나니, 원래 숫자로 돌아오는 방법이 요원했다. 따라서 4자릿수로 자르지 않고, 그냥 모든 수를 3번씩 반복하기로 했다. 왜냐하면 원소의 최댓값이 1,000이므로 최소 한 자리수일 때 3자리 숫자가 되게 하기 위해 3번을 반복하기로 했다.

따라서 [999, 555, 333, 303030, 343434]를 비교하게 된다.

// 👀 나의 최종 코드
function solution(numbers) {
  // numbers의 요소들을 문자열로 바꾸고 3번씩 반복한 값으로 바꿔주고, 문자정렬을 해서 뒤집어 준다. (문자열 정렬이므로 무조건 오름차순으로 되기 때문에 내림차순으로 바꿔주기 위해 reverse()를 사용한다.)
    const sorted = numbers.map(el => String(el).repeat(3)).sort().reverse();
  // 위의 과정을 거친 배열을 다시 원래의 길이로 되돌려준 후 숫자를 합쳐준다.
    const result = sorted.map(el => el.slice(0, el.length / 3)).join('');
  // [0, 0]로 result가 '00'일 경우를 대비해, Number타입으로 바꿔서 확인하고 이 경우 '0'을, 0의 경우가 아니라면 합쳐준 숫자 result를 반환한다.
    return Number(result) === 0 ? "0" : result
}

🌈 Reference Code

👉🏻 radix sort를 응용한 코드 (by. `패터쓴 님`)

function solution(numbers) {
  	// bucket을 만들어준다.
    const buckets = [];
	// numbers를 돌면서 요소들을 문자열로 바꾸고, 바꾼 문자열의 길이를 변수에 저장한다.
    for (const num of numbers){
        const str = String(num), len = str.length;
		// 버킷의 인덱스가 될 변수를 하나 선언.
        let idx = '';
      	// 요소의 최대 수가 1,000이므로 4자릿수 기준으로 fot문을 돌린다.
        for (let i = 0; i < 4; i++){
          	// 문자로 바꾼 숫자의 자릿수(문자열의 길이)가 i보다 크면 i만큼만, i 보다 작으면 i % 길이의 나머지 숫자의 위치의 숫자를 idx에 더해준다. 
            idx += str[len > i ? i : i % len];
        }
      // 거꾸로 정렬해주기 위해 4자리 수 중 가장 큰 9999 에서 idx 숫자를 빼준 수를 저장한다.
        idx = 9999 - idx;
		// 해당 버킷에 이미 값이 있다면 str만큼을 더해주고, 값이 없으면 str을 값으로 가진다.
        buckets[idx] = buckets[idx] ? buckets[idx] + str : str;
    }
	// 버킷들의 값을 이어붙여준다.
    const result = buckets.join('');
	// 이어붙인 숫자의 첫번째 글자가 '0'이라면 그건 numbers가 0으로만 이루어졌다는 것이므로 '0'을, 아니라면 result를 반환해준다.
    return result[0] === '0' ? '0' : result;
}

NewHa

백 번을 보면 한 가지는 안다 👀

[ᴘʀᴏɢʀᴀᴍᴍᴇʀꜱ] 정렬 - 가장 큰 수