[프로그래머스] Java : 배열 만들기2 (BFS 너비우선탐색 활용)

 

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.

만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

l	r	result
5	555	[5, 50, 55, 500, 505, 550, 555]
10	20	-1

 

---

 

안녕하세요, 이번 시간에는 BFS(너비우선탐색)를 적용한 코드를 짜보려 합니다.

먼저 너비우선탐색이란 그래프나 트리에서 가장 가까운 노드부터 탐색하는 방식입니다.

 

       1
     / | \
    2  3  4
   /|     |\
  5 6     7 8

이러한 트리 구조에서 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 순서로 탐색하는걸 의미합니다.

저는 그래서 큐(Queue)를 활용해서 코드를 작성했습니다.

 

먼저 queue에 가장 최솟값인 5를 넣어줍니다.

Queue<Integer> temp = new LinkedList<>();
        
temp.add(5);

 

그리고 while문 안에서 queue의 최신값을 .poll()해서 반환값이 조건에 맞는지 확인해줍니다.

while(!temp.isEmpty()) {
    int current = temp.poll();

    if (current >= l && current <= r) {
        answer.add(current);
    }

조건에 맞다면 answer에 넣어주기!

 

이제는 계속해서 그다음 자식노드를 만들어주면 됩니다.

반환된 값이 5였으니까 이제 [50, 55] 가 만들어지면 되겠죠?

단 반환된 값 뒤에 0을 추가한 값이 r보다 작아야한다는 점을 잊지 마세요.

if (current * 10 <= r) {
    temp.add(current * 10);
    temp.add(current * 10 + 5);
}

 

이제 queue의 값을 계속 .poll() 하고 비교해주면서 queue 안에 원소가 아무것도 없을때까지 while 문을 돌게 됩니다.

 

---

 

import java.util.*;

class Solution {
    public int[] solution(int l, int r) {
        List<Integer> answer = new ArrayList<>();
        Queue<Integer> temp = new LinkedList<>();
        
        temp.add(5);
        while(!temp.isEmpty()) {
            int current = temp.poll();
            
            if (current >= l && current <= r) {
                answer.add(current);
            }
            
            if (current * 10 <= r) {
                temp.add(current * 10);
                temp.add(current * 10 + 5);
            }
        }
        
        if(answer.isEmpty()) {
            return new int[]{-1};
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

 

이외에 제가 작성한 코드는 이곳에서도 확인하실 수 있습니다.

https://github.com/eonwy/programmers

GitHub - eonwy/programmers: 🔎 coding-test (programmers) 🔍