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

문제 설명

 

풀기 전 생각

• 최대 r자릿수만큼 String을 만들어 각각 자리에 0과 5를 대입하려고 생각
• 하지만 그 방법을 2시간 고민했지만 안 나옴..
• 고민하다가 깨달은 규칙은 처음에 5를 넣고 그 후 10을 곱하여
  앞에 들어간 숫자들을 각각 더하면 5와 0으로 만들어진 숫자들로만 구성
• 5와 0으로 만들어진 list를 l과 r로 시작점과 끝점을 찾아 배열에 복사해 주기

class Solution {
    public int[] solution(int l, int r) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int k = 5;
        int start = 0;
        int end = 0;

        while(k<=r){  // r보다 작거나 같을때까지
            list.add(k); // k값 list에 넣어주기
            int firstSize = list.size();  // 밑에서 arr.add()를 하면 실시간으로 늘어나니 미리 변수로 빼기
            for(int i = 0; i < firstSize-1; i++) { // k*10값 전까지
                if (k + list.get(i) <= r) {  // k + arr에 속해있던 값들을 각각 더해서 <=r 보다 작으면
                    list.add(k + list.get(i));  // k + arr.get(i) 값 list에 넣어주기
                }
            }
            k*=10; // 다시 k*10해주기
        }

        for(int i = 0; i < list.size(); i++){
            if(l<=list.get(i)){  // l보다 크거나 같으면 그때의 i가 시작 index
                start = i;
                break;
            }
        }
        end = list.size() - 1; // 끝 index는 size()-1

        int[] answer = new int[end - start + 1]; // 끝index - 시작index + 1 '인덱스는 0부터 시작하므로'
        if(start==0){  // 시작 index가 초기값 그대로면 범위안에 해당하는 숫자 없음
            answer = new int[] {-1};
        }else{
            for(int i = 0; i < answer.length; i++){
                answer[i]=list.get(start); // 시작index부터 끝index까지 값을 복사해줌
                start++;
            }
        }
        return answer;
    }
}

오류 및 개선

• 5개의 실패 케이스가 나왔음
• 고민해 보니 5,5처럼 시작 index가 0이고 끝 index도 0인 경우가 나옴
• 시작 index의 초기값을 -1로 주어서 시작도 못했으면 5,0으로 이루어진 숫자가 없음
• 즉 start == -1이면 -1을 리턴해줌

최종

class Solution {
    public int[] solution(int l, int r) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int k = 5;
        int start = -1; // 시작점을 -1로
        int end; // 끝점

        while(k<=r){  // r보다 작거나 같을때까지
            list.add(k); // k값 list에 넣어주기
            int firstSize = list.size();  // 밑에서 arr.add()를 하면 실시간으로 늘어나니 미리 변수로 빼기
            for(int i = 0; i < firstSize-1; i++) { // k*10값 전까지
                if (k + list.get(i) <= r) {  // k + arr에 속해있던 값들을 각각 더해서 <=r 보다 작으면
                    list.add(k + list.get(i));  // k + arr.get(i) 값 list에 넣어주기
                }
            }
            k*=10; // 다시 k*10해주기
        }

        for(int i = 0; i < list.size(); i++){
            if(l<=list.get(i)){  // l보다 크거나 같으면 그때의 i가 시작 index
                start = i;
                break;
            }
        }
        end = list.size() - 1; // 끝 index는 size()-1

        int[] answer = new int[end - start + 1]; // 끝index - 시작index + 1 '인덱스는 0부터 시작하므로'
        if(start==-1){  // 시작 index가 초기값 그대로면 범위안에 해당하는 숫자 없음
            answer = new int[] {-1};
        }else{
            for(int i = 0; i < answer.length; i++){
                answer[i]=list.get(start); // 시작index부터 끝index까지 값을 복사해줌
                start++;
            }
        }
        return answer;
    }
}

---

모범 답안 1

import java.util.stream.IntStream;

class Solution {
    public int[] solution(int l, int r) {
        int[] answer = IntStream.rangeClosed(l, r).filter(i -> {
            while (i > 0) {
                if (i % 5 != 0) return false;
                i /= 10;
            }
            return true;
        }).toArray();

        return answer.length == 0 ? new int[]{-1} : answer;
    }
}

 IntStream.rangeClosed를 사용하여 반복.
 5로 나눠 떨어지지 않으면 false, 아니면 10으로 나눠서 다 통과하면 배열에 넣기.
 나와 비슷한 풀이 같지만 좀 더 간략하고 가시성이 좋다고 느꼈다.
 하지만 시간 복잡도라는 에러 사항이 있다.

 

---

모범 답안 2

import java.util.ArrayList;

class Solution {
    public int[] solution(int l, int r) {

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i < 64; i++) {
            int num = Integer.parseInt(Integer.toBinaryString(i)) * 5;
            if (l <= num && num <= r)
                list.add(num);
        }

        return list.isEmpty() ? new int[] { -1 } : list.stream().mapToInt(i -> i).toArray();
    }
}

 10진수를 2진수로 바꾸면 1과 0만 나온다.
 거기에 5를 곱하면 0과 5로 이루어진 수로 변한다.
 제한사항이 r <= 1,000,000 이므로 i < 64로 지정했다.

 

시간 복잡도를 보니 2시간 고민한 보람을 느꼈다!