결국 구글링을 통해 해결했지만.. 개인적으로 정말 어려웠다.
가장 큰 수
문제 설명
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
해결한 코드
function solution(numbers){
var answer = numbers.map(e => e + "").sort((a,b) => (b+a) - (a+b)).join('')
return answer
}내가 고민하며 구현한 코드보다 훨씬 간결하고 무엇보다 채점에서 통과했다.
위 코드에서 나에게 다소 생소했던 부분은 sort((a,b) => (b+a) - (a+b)) 인데, 나는 주로 sort((a,b) => return a-b)와 같이 단순 오름차순과 내림차순만 사용했기 때문이다.
만약 numbers로 [12, 121]이 들어온다면,
- 문자열화: numbers = ['12', '121']
--> b = '12', a = '121- 정렬: ('12121') - ('12112')
2-1. 이렇게 계산하면 9가 나올 것이다.
2-2. 양수가 나오면 배열을 그대로 두는 건가? 출력해보았을 때 배열은 ['12', '121'] 그대로였다.
--> 확인 결과 그대로 두는거 맞다.- 붙이기: answer = '12121'
이렇게 출력된다.
반대로 numbers = [121, 12]가 들어온다면,
- 문자열화: numbers = ['121', '12']
--> b: '121', a = '12'- 정렬: ('12112') - ('12121')
2-1. 이렇게 계산하면 -9가 나온다.
2-2. 음수가 나오면 배열을 바꿔? 출력해보았을 때 배열은 ['12', '121'] 로 바뀌었다.
--> 확인 결과 바꾸는거 맞다.- 붙이기: answer = '12121'
그에 반해 나는 꽤나 복잡하게 생각했다. 이제부터는 나의 복잡했던 시행착오를 정리하고자 한다.
나의 코드
function solution(numbers){
var answer = ''
var copy_numbers = numbers.slice()
var copy_array = []
var mok, nmg, nmg2 = 0
var answer_array = []
for(var i=0; i<copy_numbers.length; i++){
if (10 <= copy_numbers[i] && 100 > copy_numbers[i]) {
// 만약 원소가 두자리수이면
mok = Math.floor(copy_numbers[i] / 10)
nmg = copy_numbers[i] % 10
nmg2 = -1
copy_numbers[i] = mok
} else if (100 <= copy_numbers[i] && 1000 > copy_numbers[i]) {
// 만약 원소가 세자리수이면
mok = Math.floor(copy_numbers[i] / 100)
nmg = copy_numbers[i] % 100
if (nmg < 10) {
nmg2 = nmg % 10
nmg = 0
} else {
nmg2 = nmg % 10
nmg = Math.floor(nmg / 10)
}
copy_numbers[i] = mok
} else if (1000 == copy_numbers[i]) {
// 원소 4자리수는 1000밖에 없다. 1000이하의 수만 들어오기 때문이다.
nmg = 0
copy_numbers[i] = 1
nmg2 = -1
} else {
// 원소가 한자리수면
nmg = copy_numbers[i] % 10
nmg2 = -1
}
copy_array.push({
idx: i,
val: copy_numbers[i],
nmg: nmg,
nmg2: nmg2
})
}
// numbers를 복제한 copy_numbers에 원소를 {idx: 0, val: 1, nmg: 0, nmg2: 1} 이런식으로 만들어 저장했다.
/* nmg2를 만든건 [12, 121]와 같이 첫번째, 두번째 자리의 숫자가 중복되는 경우를 생각해주기 위해서였다.
이 수들이 위 과정을 거치면 [{idx: 0, val: 1, nmg: 2, nmg2: -1}, {idx: 1, val: 1, nmg: 2, nmg2: 1}]로 저장된다. */
copy_array.sort((a, b) => {
if (b.val == a.val) { // val 값이 같으면
if (b.nmg == a.nmg) { // val, nmg 값이 같으면
if (a.nmg2 > b.nmg2) { //a의 nmg2가 더 크면
if (a.nmg > a.nmg2) { //nmg2가 nmg보다 작으면
return a.nmg2 - b.nmg2 // nmg2 오름차순으로 정렬
} else if (a.nmg2 >= a.val) { // nmg2가 nmg보다 크고 val보다 크거나 같으면
return b.nmg2-a.nmg2 // nmg2 내림차순 정렬
} else { // nmg2가 nmg보다 크고 val보다 작으면
return a.nmg2 - b.nmg2 // nmg2 오름차순 정렬
}
} else { a의 nmg2가 더 크지 않다면
if (b.nmg > b.nmg2) {
return a.nmg2 - b.nmg2
} else if (b.nmg2 >= b.val) {
return b.nmg2-a.nmg2
} else {
return a.nmg2-b.nmg2
}
}
// 정렬 방법은 위랑 같은데 헷갈리기 싫어서 적었던 것 같다.
} else { // nmg값이 같지 않으면 nmg 내림차순
return b.nmg - a.nmg
}
} else { // val값이 같지 않으면 val 내림차순
return b.val - a.val
}
})
// 최대수가 나올 수 있도록 정렬하고자 했다.
for (var j = 0; j < numbers.length; j++) {
answer_array.push(numbers[copy_array[j].idx])
}
// copy_array의 idx에 적힌 순서대로 numbers의 원소를 찾아 answer_array에 담았다.
if(!answer_array.some((e)=> e !== 0)){ // 근데 원소가 모두 0이면
answer = '0' // 그냥 0을 반환
} else {
answer = answer_array.join('') // 문자열로 붙여서 반환
}
return answer
}ㅋㅋㅋㅋ 열심히 생각했고, 사람들이 올려놓은 테스트 케이스도 모두 통과했지만 채점에선 다 실패했다.
특히 1~6번.. '대체 왜 계산되지 못했을까' 고민했지만 결국 답은 찾지 못했다.
개인적으로 가장 어려웠고 헷갈리고 시행착오를 많이 겪었던 부분은 sort였다.
아마도 내 코드가 통과하지 못한 건 sort를 제대로 하지 않아서가 아닐까..
내가 생각한 알고리즘
- 만약, numbers에 [12, 121], [40, 404]와 같은 숫자들이 온다면
- 12 = {idx: 0, val: 1, nmg: 2, nmg2: -1}, 121 = {idx: 0, val: 1, nmg:2, nmg: 1}이 된다.
- 40 = {idx: 0, val: 4, nmg: 0, nmg2: -1}, 404 = {idx: 1, val: 4, nmg: 0, nmg2: 4}이 된다.
- 나는 여기서 (조금은 이상한) 규칙을 하나 발견했는데,
4-1. (첫 번째, 두번째 자리 숫자가 같은 두 수 중에) 세자리 원소의 맨 끝자리 수가 두자리 수 원소의 맨 앞자리 수보다 작으면 뒤로, 같거나 크면 앞으로 가야 큰 수를 만들 수 있었다.
4-2. 그러나 맨 끝자리 수가 두번째 자리 수보다 작으면 뒤로 가야 했다.
4-3. 즉, val, nmg가 같은 두 수 중에서 a의 nmg2가 b의 val보다 작으면 뒤로, 같거나 크면 앞으로 가는 것. 하지만, a의 nmg가 nmg2보다 크면 뒤로 갈 것.
지금 쓰고 보니까 이게 과연 발견한 '규칙'이 맞는지 모르겠다... 규칙이라 해도 될런지..
코딩을 공부하면서 느끼지만, 진짜 다양한 사람들이 작성하는 알고리즘의 매력에 감탄한다. 다양한 함수를 사용해 간결한 코드를 짜내는 것도 대단하다 느끼지만, 종종 어쩜 저렇게 생각해서 풀었을까 싶은 코드들도 많이 봤다. 사실 이 문제를 해결한 코드도 마찬가지... 난 저렇게 정렬해서 풀 생각도 못했는데..
sort의 또다른 활용을 맛볼 수 있어서 좋았다 ! 반복해서 내 것으로 만들어야지 !
