프로그래머스 > 코딩테스트 연습 > 탐욕법(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();
for (let i = 0; i < number.length; i++) { num[i] = Number(number.substring(i, i+1)); }
var count = num.length - k; var start = 0;
while (count > 0) { start = func(num, start, count); count--; }
return answer.join('');
function func(n, start, count) { var max = '0'; var index = start; --- 중략 --- }
function func(n, start, count) { --- 중략 --- for (let i = start; i <= n.length - count; i++) { if (max < n[i]) { max = n[i]; index = i; } } --- 중략 --- }
자바로 풀었을 때보다 시간 복잡도가 늘어났고, 탐욕법 문제인데 이게 탐욕법에 들어갈지 의문이기도 함... 알고리즘은 어렵다...