[JavaScript] 프로그래머스 - 큰 수 만들기 (2단계)

📝 문제

프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 큰 수 만들기

---

📝 답안

📌 작성 코드

var answer;
function solution(number, k) {
    answer = new Array();
    var num = new Array();
    
    for (let i = 0; i < number.length; i++) {
        num[i] = Number(number.substring(i, i+1));
    }
    
    var start = 0;
    var count = num.length - k;
    
    while (count > 0) {
        start = func(num, start, count);
        count--;
    }
    
    return answer.join('');
}

function func(n, start, count) {
    var max = '0';
    var index = start;
    for (let i = start; i <= n.length - count; i++) {
        if (max < n[i]) {
            max = n[i];
            index = i;
        }
    }
    
    answer.push(max);
    return index + 1;
}

---

📌 결과

테스트 1 〉 통과 (0.13ms, 30.2MB)
테스트 2 〉 통과 (0.19ms, 30MB)
테스트 3 〉 통과 (0.15ms, 30MB)
테스트 4 〉 통과 (0.30ms, 30.2MB)
테스트 5 〉 통과 (1.28ms, 32.8MB)
테스트 6 〉 통과 (16.24ms, 32.9MB)
테스트 7 〉 통과 (31.37ms, 34.5MB)
테스트 8 〉 통과 (207.01ms, 37MB)
테스트 9 〉 통과 (40.57ms, 55.9MB)
테스트 10 〉 통과 (6825.29ms, 55.7MB)
테스트 11 〉 통과 (0.11ms, 29.9MB)
테스트 12 〉 통과 (0.14ms, 30.1MB)

---

📌 코드 풀이

var answer = new Array();

• String으로 문자열 붙이기를 하면 시간을 많이 차지 하기 때문에 일단 배열로 선언

for (let i = 0; i < number.length; i++) {
	num[i] = Number(number.substring(i, i+1));
}

• 한 자리씩 잘라가면서 Number형으로 변환하고, 배열에 담기

var count = num.length - k;
var start = 0;

• count : 만들어야 할 숫자의 길이
• start : 탐색을 시작하는 위치

while (count > 0) {
	start = func(num, start, count);
	count--;
}

• count가 0이 될 때까지 while문 반복하기
• func(int배열, 탐색 시작할 위치, 만들어야할 숫자 길이)
• func함수 리턴값으로 시작 위치 리셋
• func함수를 호출 할 때마다 숫자 하나씩 answer에 더해지기 때문에 구해야할 숫자 길이인 count는 1씩 줄어듦

return answer.join('');

• answer은 배열로 선언되어 있기 때문에 리턴할 땐 join으로 배열을 합쳐야 함

function func(n, start, count) {
    var max = '0';
    var index = start;
	--- 중략 ---
}

• max : 가장 큰 수를 담을 변수. 임시로 0으로 할당
• index : func함수 리턴값. 임시로 start로 할당

function func(n, start, count) {
	--- 중략 ---
    for (let i = start; i <= n.length - count; i++) {
        if (max < n[i]) {
            max = n[i];
            index = i;
        }
    }
	--- 중략 ---
}

• for문의 범위는 start부터 (길이 - 구해야할 자리 수) 까지임.
• 범위 내에서 가장 큰 값 구하기

---

📌 설명 한 눈에 파악하기

---

📝 후기

자바로 풀었을 때보다 시간 복잡도가 늘어났고, 탐욕법 문제인데 이게 탐욕법에 들어갈지 의문이기도 함... 알고리즘은 어렵다...