[프로그래머스] 탐욕법(Greedy) _ 큰 수 만들기

2021_08_29 알고리즘 스터디 문제 풀이

문제 URL

코딩테스트 연습 - 큰 수 만들기

 

문제

 

문제를 읽지마자 이건 조합알고리즘을 재귀로 구현하고, 그 중 제일 큰 수를 리턴하면 되겠다라고 생각이 들었다.

1차 문제풀이

function combination(letters, pickNum) {
    let arr = [];
    
    function aux(str, lastIdx) {
        if (str.length === pickNum) {
            arr.push(str);
            return;
        }
        
        for (let i = lastIdx + 1; i < letters.length; i++) {
            aux(str + letters[i], i)
        }
    }
    aux("", -1)
    return arr;
}

function solution(number, k) {
    const arr = combination(number, number.length - k);
    return String(Math.max(...arr))
}

combination 재귀함수를 사용해서 조합을 출력하고, 그 중 가장 큰 값을 리턴하는 코드였다.

재귀함수로 인해서 시간 복잡도 O(2^n)의 코드여서 그런지 채점 결과 런타임에러가 다수 발견되었다.

 

이 과정에서 탐욕법을 통해서 시간 복잡도를 최소화하려고 되게 오랜 시간을 생각하고 있었다.

탐욕법이라는 개념이 주어진 상황에서 가장 최적이라고 생각되는 해들을 조합한 결과인 건데, 이런 사고 과정이 약간 낯설었다.

마지막 수도코드

stack 빈배열을 선언한다. (유효한 숫자들을 담기 위함)

number를 순회한다. (모든 숫자를 비교하기 위함)
	// 앞 인덱스의 값보다 바로 뒤 인덱스의 값이 더 크면 앞에있는 아이를 제거해야 함
	만약, stack의 마지막 인덱스의 값이 number[i]의 값보다 작다면, while문으로 진행
    	(stack에 pop 메소드가 사용되어 마지막 요소가 바뀔 수 있기 때문에 다시 확인하기 위해 while문 처리)
    	stack.pop을 사용하여 제일 뒤에있는 요소를 제거한다
        k의 값을 1 감소시킨다.
        
    stack에 number[i]의 값을 추가한다 (push)
 
 k의 값이 남아있는 경우가 있을 수 있음
 stack.slice 메소드를 사용, stack.length - k 만큼 제거한 값을 join으로 이어붙여 리턴한다

 

마지막 문제풀이

function solution(number, k) {
    let stack = [];
    
    for (let i = 0; i < number.length; i++) {
        const now = number[i]
        
        while (k > 0 && stack[stack.length - 1] < now) {
            stack.pop();
            k--;
        }
        stack.push(now);
    }
    return stack.slice(0, stack.length - k).join("")
}

 

stack 빈배열을 선언하여 값을 계속 추가하고, 마지막 요소를 비교하며 이전 인덱스의 값이 현재 인덱스의 값보다 작다면 그를 제거하고, k의 숫자를 감소시키는 로직으로 코드를 구현했다.

시간 복잡도 O(n^2)