[파이썬, Java] 1526. 가장 큰 금민수

문제

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

N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다.

예제 입력 1 

100

예제 출력 1 

77

 

 

🍟 나의 풀이

N=int(input())
ans=0

def dfs(num) :
    global ans
    if int(num) > N :
        return
    elif ans < int(num) :
        ans=int(num)

    for i in ['4', '7'] :
        num+=i
        dfs(num)
        num=num[:-1]

dfs('4')
dfs('7')
print(ans)

백트래킹 풀이

4로 시작, 7로 시작 두 가지를 다 하기 위해서 함수 호출이 2번이다.

 

 

N=int(input())
ans=0

def find(i) :
    for s in str(i) :
        if s not in ['4', '7'] :
            return False
    return True

for i in range(4, N+1) :
    if find(i) :
        ans=int(i)

print(ans)

완전탐색 풀이

위의 백트래킹 풀이가 효율이 더 좋음

find 메소드에서 4 또는 7이 들어있는지 한 문자씩 확인한다.

4부터 N+1까지 반복하면서 4와 7로 이루어진 수를 찾는다.

수가 순차적으로 커지므로 find(i)가 true면 ans를 갱신한다.

 

 

import java.io.*;

public class Main{
    static int N;
    static int answer;

    public static void main(String[] args) throws Exception{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(in.readLine());
        answer=4;
        dfs("4");
        dfs("7");
        System.out.println(answer);

    }

    public static void dfs(String s){
        if(Integer.parseInt(s) > N){
            return;
        }else if(Integer.parseInt(s) > answer){
            answer=Integer.parseInt(s);
        }

        dfs(s+"4");
        dfs(s+"7");
    }
}

dfs 풀이

파이썬으로 푼 다른 사람 풀이의 알고리즘을 자바로 구현

 

 

🐹 다른 사람 풀이

N=int(input())
X=0

def dfs(u) :
    global X
    if int(u) > N :
        return
    X=max(X, int(u))
    dfs("4"+u)
    dfs("7"+u)

dfs("4")
dfs("7")
print(X)

dfs 풀이

 

 

import java.io.*;

public class Main{
    static int N;
    static int answer;

    public static void main(String[] args) throws Exception{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(in.readLine());

        dfs(4);
        dfs(7);

        System.out.println(answer);

    }

    public static void dfs(int number){
        if(number > N){
            return;
        }
        answer=Math.max(answer, number);
        dfs(number*10+4);
        dfs(number*10+7);
    }
}

아이디어가 좋다.

나는 문자열 number에 "4" 또는 "7"을 이어붙였는데..

number*10+4를 하면 문자열에서 숫자 또는 숫자에서 문자열로 변환하지 않아도 되니까 좋다.

 

 

 

문제 출처 👉 백준