백준 1527번) 금민수의 개수 (JAVA)

https://www.acmicpc.net/problem/1527

1527번: 금민수의 개수

 

#문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

 

#알고리즘

• 부루트포스 알고리즘

 

#난이도

Silver 1

 

#풀이방법

문제 자체는 어렵지 않다. 문제만 본다면 왜 이 문제가 실버1이나 되는지 의문이 들까 싶었다. 하지만 코드를 짜고 try를 할 수록 왜 난이도를 실버1로 설정했는지 알 수 있는 문제였다. A와 B와 사이를 모두 돌려 4와 7로 이루어져 있는지 체크해주는 boolean 메소드를 이용해 풀면 시간초과가 나온다. 

 

이럴경우 부루트포스라고 모든 수를 탐색하는 것이 아니라 4와 7로 이루어진 숫자들만 검사하여 그 수가 A와 B에 있는지만 체크해주면 된다. 즉 부르트포스라고 무지성으로 모든 경우의 수를 탐색하는 것이 아닌 완전탐색의 범위를 줄이는 것이

부루트포스의 포인트임을 알게 해주었다.

 

4와 7만 탐색하는 경우는 

queue.add(n*10+4);
queue.add(n*10+7);

다른 분들은 dfs로 재귀함수로 호출하여 푸셨지만 나같은 경우는 bfs로 queue를 이용하여 체크하기로 하였다.

 

처음에 4와 7을 넣고 위 처럼 queue에 넣고 A와 B사이에 있는 경우 횟수를 세주고 B를 넘을 경우, 끊어준다.(continue)로..

 

전체적인 코드를 보면..

 

#전체 코드

 

import java.util.*;
 
public class Main {
    
    
    static Queue<Long> queue = new LinkedList<>();
    
    static int gold_num = 0;
    static int A;
    static int B;
 
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        
        A = sc.nextInt();
        B = sc.nextInt();
        
        //bfs로 구현한다.
        queue.add((long)4);
        queue.add((long)7);
        
        
        while(!queue.isEmpty()) {
            
            long n = queue.poll();
            
            
            if( n > B)
                continue;
            
            if(A <= n && n <= B)
                gold_num++;
        
            //System.out.println(n);
            
            queue.add(n*10+4);
            queue.add(n*10+7);
            
        }
        
        System.out.println(gold_num);
 
    }
    
    
 
}

 

문제를 풀면서 지속적인 메모리초과가 나왔다. 왜 메모리 초과가 나왔지?라고 깊게 생각해보니, 입력받을 수 있는 A와 B가

 queue.add(n*10+4)나 queue.add(n*10+7)이 Integer의 범위를 초과할수 있기 때문이다.

그렇기 때문에 메모리 초과 문제가 생긴 것 같다.

 

그렇기 때문에 내 코드의 모든 int를 long으로 바꾸고 다시 제출하니 정상적으로 정답이 나오게 되었다.