[프로그래머스] 배열 만들기 2 - JAVA[자바]

[프로그래머스] 배열 만들기 2 - JAVA[자바]

문제링크

문제

 

전체 코드

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();

    public int[] solution(int l, int r) {
        for (int i = 1; i <= 6; i++) { 
            dfs(l, r, i, "");
        }

        if (list.isEmpty()) {
            return new int[]{-1};
        } else {
            Collections.sort(list);
            return list.stream().mapToInt(i -> i).toArray();
        }
    }

    private void dfs(int l, int r, int length, String num) {
        if (length == num.length()) {
            int number = Integer.parseInt(num);
            if (number >= l && number <= r) {
                list.add(number);
            }
            return;
        }

        dfs(l,r,length,num+"5");
        if (!num.equals("")) {
            dfs(l,r,length,num+"0");
        }
    }
}

 

문제 이해

• 주어진 범위(l,r) 내에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 찾아내는 것.
• 그런 정수가 없다면 -1을 반환하고, 있으면 오름차순으로 배열에 담아 반환한다.

 

로직구성

1. 재귀적인 방법을 사용하여 각 자릿수에 대해 0 또는 5를 추가하고 그 수가 l과 r 사이에 있는지 확인한다.
2. 숫자의 길이가 목표하는 길이와 같다면 그 숫자가 범위 내에 있는지 확인하고 리스트에 추가한다.
3. 아니라면 현재 문자열 뒤에 '5'와 '0'을 각각 붙여서 재귀적으로 탐색한다.

 

변수 및 자료 구조 선택

List<Integer>list : 결과를 저장할 리스트

int l, int r : 입력으로 주어진 범위

int length : 생성할 숫자의 길이

String num : 현재까지 만들어진 숫자 문자열

 

문제 풀이

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>(); // 결과를 저장할 리스트를 초기화한다.

    public int[] solution(int l, int r) {
        for (int i = 1; i <= 6; i++) { // 숫자의 최대 길이는 6이므로, 길이 1부터 6까지 순회한다.
            dfs(l, r, i, ""); // 각 길이에 대해 재귀 함수를 호출.
        }

        if (list.isEmpty()) { // 만약 리스트가 비어 있다면 -1만 담긴 배열을 반환한다.
            return new int[]{-1};
        } else {
            Collections.sort(list); // 결과 리스트를 오름차순으로 정렬하고,
            return list.stream().mapToInt(i -> i).toArray(); // 정수 배열로 변환하여 반환한다.
        }
    }

    private void dfs(int l, int r, int length, String num) {
        if (length == num.length()) { // 현재 문자열의 길이가 목표하는 길이와 같다면
            int number = Integer.parseInt(num); 
            if (number >= l && number <= r) { 
                list.add(number); // 해당 숫자가 범위 내에 있다면 리스트에 추가한다.
            }
            return;
        }

        dfs(l,r,length,num+"5"); // 현재 문자열 뒤에 '5'를 붙여서 재귀적으로 탐색. 
        if (!num.equals("")) { 
            dfs(l,r,length,num+"0");  //'0'은 첫 자리에 올 수 없으므로 num이 비어있지 않을 때만 '0'을 붙인다.
        }
    }
}