[Programmers] 정렬: Level 2 - 가장 큰 수 (javascript) 문제 풀이

문제

원본 사이트 : programmers.co.kr/learn/courses/30/lessons/42746?language=javascript

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

 

문제 설명

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

 

풀이

1. sort() 메서드의 compareFunction을 직접 만들어 비교 - (실패)

function solution(numbers) {
    var answer = '';
    numbers.sort((a, b) => {
        const stringA = a.toString().replace(/(0+$)/, "");
        const stringB = b.toString().replace(/(0+$)/, "");
        
        if(stringA == stringB){
            return a - b;
        }
        else{
            if(stringA > stringB)   return -1;
            else if(stringA < stringB)  return 1;
            else    return 0;
        }
    });
    for(let i=0; i<numbers.length; i++){
        answer += numbers[i];
    }
    return answer.replace(/(^0+)/, "0");
}

• numbers.sort() : 두 수를 비교해 내림차순으로 정렬
• stringA, stringB : a, b를 각각 string으로 변환한 뒤, 문자열 끝에 나오는 '0'을 모두 제거
• stringA와 stringB가 같으면 숫자로 비교해 작은 숫자를 더 앞에 오도록 sort (a: 1, b: 10인 경우 a가 더 큰 숫자가 될 수 있도록)
• stringA와 stringB가 같지 않은 경우에는 string 값으로 비교해 내림차순 정렬((stringB - stringA)을 return 하게 되면 숫자로 인식해서 틀린 결과가 나오므로 if문으로 비교)
• for문을 돌며 numbers의 값들을 answer에 붙이기
• 0만 있는 경우, answer 값이 0...0이 되므로 문자열의 첫번째에 반복해서 나오는 0...0을 0으로 replace

→ 이렇게 하면 테스트 케이스와 내가 추가한 몇 개의 테스트 케이스는 모두 통과하는데, 실제로 코드를 제출하면 7개의 케이스에서 '실패'하게 됨

 

2. String으로 변환한 뒤, 두 개의 합으로 순서 지정 - (+13)

function solution(numbers) {
    var answer = numbers.map((number) => number.toString()).sort((a, b) => (b+a) - (a+b)).join("");
    return answer.replace(/^0+/, "0");
}

• map() 메서드를 통해 numbers의 요소들을 모두 string으로 변형
• string으로 변형한 numbers를 sort() 메서드를 통해 정렬
• a+b와 b+a로 비교해 내림차순으로 정렬
• join() 메서드를 통해 배열의 모든 요소를 문자열로 이어붙임
• 0만 있는 경우, answer 값이 0...0이 되므로 문자열의 첫번째에 반복해서 나오는 0...0을 0으로 replace해서 결과 return

정렬할 때, 단순히 a와 b로만 비교하는 게 아니라 a+b와 b+a로 비교하면 문자열로 바꿨기 때문에 숫자의 합이 아닌, 문자열의 합을 가지고 비교하게 된다.
예를 들어 a=1과 b=10을 비교할 경우, (a+b)는 11이 아닌 110이 되고, (b+a)는 101이 된다.
이 두 문자열을 비교해 더 큰게 앞에 오도록 (b+a) - (a+b)를 return해준다.

 

후기

이 문제는 두 문자열을 이어서 비교하는 (b+a) - (a+b)가 핵심이다.
이 방법만 잘 생각이 나면 코드는 두줄로 끝이 나는데, 어렵게 생각하면 계속 꼬이게 되고 시간만 낭비하게 되는 그런 문제였다.

결국 처음 시도하던 방법을 포기하고 구글링을 통해 (b+a) - (a+b)를 깨닫게 되었지만, 이런 방법이 있다는 것을 알게 된 게 중요하다고 생각한다.
앞으로 이걸 종종 써먹어야지...

그리고 프로그래머스 문제를 풀수록 map()이나 filter(), sort() 등의 메서드들을 많이 쓰게 되어서 사용법을 익힐 수 있어서 좋은 것 같다.