[프로그래머스] Lv.0 배열 만들기 2

문제 설명

주어진 범위 [l, r] 내에서 숫자들이 0과 5로만 이루어진 숫자를 찾아 오름차순으로 정렬하여 배열로 반환하는 문제입니다. 만약, 그런 숫자가 없다면 -1이 담긴 배열을 반환합니다.

문제 조건

•	숫자들은 0과 5로만 이루어져 있어야 합니다.
•	범위는 [l, r]으로 주어지며 1 ≤ l ≤ r ≤ 1,000,000 입니다.

문제 해결 전략

이 문제를 해결하기 위해선 0과 5로만 이루어진 숫자를 찾아야 한다. 범위내의 모든 숫자들을 확인하면서 배열에 담기로 결정~

1.	숫자를 문자열로 변환
	•	각 숫자를 문자열로 변환하여 각 자릿수를 확인
    
2.	문자 확인
	•	숫자의 각 자릿수가 0 또는 5로 이루어졌는지 확인
    
3.	조건에 맞는 숫자 저장
	•	0과 5로만 이루어진 숫자라면 리스트에 저장
    
4.	리스트를 배열로 변환
	•	조건에 맞는 숫자가 없다면 [-1을 반환]하고, 조건에 맞는 숫자들을 배열로 변환하여 반환
    
    
    

최종 코드

import java.util.*;

class Solution {
    public int[] solution(int l, int r) {
        List<Integer> list = new ArrayList<>();

        // l에서 r까지의 숫자 중 0과 5로만 이루어진 숫자 찾기
        for (int i = l; i <= r; i++) {
            String str = Integer.toString(i);
            boolean valid = true;

            // 각 자릿수를 확인하여 0 또는 5로 이루어졌는지 검사
            for (char c : str.toCharArray()) {
                if (c != '0' && c != '5') {
                    valid = false;
                    break;
                }
            }

            // 조건에 맞는 숫자 리스트에 추가
            if (valid) list.add(i);
        }

        // 조건에 맞는 숫자가 없다면 -1 반환
        if (list.isEmpty()) {
            return new int[]{-1};
        }

        // 리스트를 배열로 변환하여 return
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

1. 이진법을 생각해본다. 0과 5로만 이루어진 숫자라고 하였으니 그 모양이 이진법과 같다.

2. DFS알고리즘을 이용한다. 작은 수 부터 차례대로 생성하려면 BFS방식이 적합함. 큐를 사용하여 0과 5로 시작한 뒤, 새로운 숫자를 만들어나가는 방법으로 탐색해보기.

import java.util.*;

class Solution {
    public int[] solution(int l, int r) {
        // 결과를 저장할 리스트
        List<Integer> result = new ArrayList<>();
        
        // BFS를 위한 큐
        Queue<String> queue = new LinkedList<>();
        queue.add("5");  // 5로 시작
        queue.add("0");  // 0도 포함
        
        // BFS로 0과 5로 이루어진 숫자 생성
        while (!queue.isEmpty()) {
            String current = queue.poll();
            int num = Integer.parseInt(current);
            
            // 생성된 숫자가 범위 안에 있는지 확인
            if (num >= l && num <= r) {
                result.add(num);
            }
            
            // 숫자가 r보다 커지면 더 이상 탐색하지 않음
            if (num > r) continue;
            
            // 현재 숫자에 0과 5를 추가하여 새로운 숫자 생성
            queue.add(current + "0");
            queue.add(current + "5");
        }
        
        // 조건에 맞는 숫자가 없으면 -1 반환
        if (result.isEmpty()) {
            return new int[]{-1};
        }

        // 리스트를 배열로 변환하여 반환
        int[] answer = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }
}