문제 설명
정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.
제한사항
- 1 ≤ l ≤ r ≤ 1,000,000
입출력 예
l r result
| 5 | 555 | [5, 50, 55, 500, 505, 550, 555] |
| 10 | 20 | [-1] |
입출력 예 설명
입출력 예 #1
- 5 이상 555 이하의 0과 5로만 이루어진 정수는 작은 수부터 5, 50, 55, 500, 505, 550, 555가 있습니다. 따라서 [5, 50, 55, 500, 505, 550, 555]를 return 합니다.
입출력 예 #2
- 10 이상 20 이하이면서 0과 5로만 이루어진 정수는 없습니다. 따라서 [-1]을 return 합니다.
풀이
이 문제의 경우에는 for문으로 순회만 해서는 풀 수 없다.
r의 최대가 백만이기 때문에 수가 백만이라면 전부 순회하는데 한참~~ 걸린다.
그래서 살짝쿵 물어보니 queue(큐) 라는 자료구조를 구현한 다음 문제를 풀어야 한다고 한다.
구현 코드
import java.util.*;
class Solution {
public int[] solution(int l, int r) {
Queue<String> que = new LinkedList<>();
List<Integer> list = new ArrayList<>();
que.add("5");
while(!que.isEmpty()){
String str = que.poll();
int tmp = Integer.parseInt(str);
if(tmp>r)
break;
if(tmp>=l)
list.add(tmp);
que.add(str+"0");
que.add(str+"5");
}
if(list.isEmpty()){
list.add(-1);
}
// System.out.println(list.size());
int[] answer = new int[list.size()];
for(int i=0; i<answer.length; i++){
answer[i] = list.get(i);
}
return answer;
}
}
큐 라는 구조는 구현하기에는 코딩테스트의 목적에 맞지 않으니 Java에서 기본적으로 지원하는 큐 class를 사용하도록 하자.
우선 que를 하나 선언해준다.
이 때 String으로 선언해주는 이유는 문제에서 0과 5로만 이루어진 정수를 받기 때문에 문자열로 5와 0을 붙이면 간단하게 수를 만들 수 있기 때문에 이렇게 풀어주었다.
(어차피 나중에 정수로 바꿔주면 되기 때문이다.)
여기에 가장 기본이 되는 수인 5를 큐에다가 삽입해준다.
이제 반복문으로 큐에 있는 5를 꺼내주고 정수로 형변환을 해준 변수에다가 담아준다.
여기에 조건문을 사용해서 반복의 조건을 정해준다.
- tmp가 조건에 있는 r보다 작다면 반복을 종료한다.
- tmp가 l보다 크다면 선언한 리스트에다가 값을 넣어준다.
- 큐에다가도 5와 0으로만 이루어진 정수이기 때문에 각각 5와 0을 더해준 값을 큐에다가 넣는다.
- 이렇게하면 50,55 가 큐에 들어가고 다음 반복에는 500,505,550,555 가 큐에 다시 들어가게 된다.
- 마지막엔 r보다 수가 커지기 때문에 반복이 종료된다.
이제 정적배열을 하나 선언해서 list의 size() 메서드, 즉 리스트 길이만큼의 배열을 선언해준다.
(굳이 정적배열을 선언하는 이유는 기존 문제의 틀인 정적배열 return 을 깨지 않고싶기 때문)
이제 for 문으로 순회하며 각 배열의 인덱스에 리스트의 요소를 넣어주면 끝 !
문제 후기
슬슬 자료구조에 대해 알지 못하면 문제를 해결할 수 없는 문제들이 등장하고 있다.
이렇게 풀면서 자연스럽게 자료구조에 대해 공부하며 풀면 앞으로 많은 도움이 될 듯 하다.