프로그래머스 배열 만들기 2

문제 설명

정수 l과 r이 주어졌을 때, l 이상 r 이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 반환하라.
조건을 만족하는 정수가 없을 경우 [-1]을 반환한다.

 

문제 풀이

핵심 아이디어

• 숫자를 직접 생성해보되, 0과 5로만 이루어진 숫자만 생성한다.

• 숫자를 문자열로 이어 붙이는 방식으로 탐색(DFS)하며, 조건에 맞는 경우만 수집한다.

• 시작점은 "5"부터 재귀적으로 "0"과 "5"를 붙여 나가며 l ≤ num ≤ r 인 숫자들을 결과 배열에 추가한다.

 

JavaScript 구현

function solution(l, r) {
    const answer = [];
    function genNum(current) {
        const num = Number(current);
        if (num > r) return;
        if (num >= l) answer.push(num);
        genNum(current + "0");
        genNum(current + "5");
    }
    genNum("5");  // 조건에 맞는 시작 숫자
    answer.sort((a, b) => a - b);
    return answer.length ? answer : [-1];
}

해설

• genNum은 문자열로 숫자를 만들며 "0" 또는 "5"만을 덧붙인다.

• 만들어진 숫자가 r보다 크면 더 이상 탐색하지 않음으로써 가지치기를 한다.

• 이 방식은 0~1,000,000 범위 내에서 0과 5로만 이루어진 수의 개수가 제한적이므로 성능적으로도 효율적이다.

• 중요한 점은 초기 호출 시 l을 넣는 것이 아니라 조건을 만족하는 숫자("5")부터 시작해야 한다는 것