adfsfsf   1년 전

이 문제만이 아니라, 다른 문제들에서도 적용 가능한 방식입니다.

이 문제의 경우, '입력값보다 작거나 같은 수들 중, 가장 큰 금민수'를 구하는 것을 요구하고 있습니다.
이에 많은 분들께서 '입력값을 기준으로 가장 큰 금민수를 찾기'를 시도하게 됩니다 - 저도 그랬고요.
이런 방법은 크게 2가지가 존재합니다.
첫째는 입력값부터 내려가면서, 금민수가 나올 때까지 완전탐색을 하는 방법입니다.
둘째는 규칙을 찾아, 복잡한 조건문을 만드는 방법입니다.
첫 번째 방법은 시간 복잡도가 심하게 커질 위험을 감수해야 됩니다.
두 번째 방법은 규칙이 있더라도 너무 복잡할 수 있습니다.

그렇기에, 때로는 반대로 생각해보는 것도 필요합니다.
'금민수'는 '모든 자리가 2가지 수 중 하나만으로 구성되는 자연수'입니다.
따라서 '입력 값 범위 내의 모든 금민수'를 구하고, 그 금민수들과 비교를 하는 것은 충분히 빠른 방법입니다.
'금민수를 구하는 과정'에서부터 작은 수부터 배열에 들어가도록 하면 별도의 정렬도 필요 없겠죠.
범위 내의 금민수들을 위해서는 BFS를 사용하시면 됩니다.
["4", "7"]을 시작 queue로 주고, 범위를 벗어나지 않을 때까지, queue의 가장 앞의 수에 대해 4를 붙인 수와 7을 붙인 수를 계속 추가하면 되겠죠.

PS. 현재 알고리즘 분류에는 BFS가 없습니다.
'난이도 기여'를 보니 숫자 범위가 충분히 작다는 이유만으로 다들 브루트포스를 선택하셨더군요.

댓글을 작성하려면 로그인해야 합니다.