[백준] 1526번: 가장 큰 금민수(시뮬레이션)

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

1526번: 가장 큰 금민수

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();

		// N 부터 만족하는 수까지 감소하면서 찾는다.
		for(int i=N; i>=4; i--) {
			boolean flag = true;
			int num = i;
			while(num != 0) {
				// num의 끝에 자리가 4이거나 7일경우 => 다음 자리수를 찾기 위해 10으로 나눔
				if(num % 10 == 4 || num % 10 == 7)
					num /= 10;
				// num이 4나 7로 나누어 떨어지지 않는경우 => 조건 만족 X, 다음수 찾기 위해 while문 탈출
				else {
					flag = false;
					break;
				}
			}
			
			if(flag) {
				System.out.println(i);
				break;
			}
		}
		scan.close();
	}

}

풀이

단순한 구현문제 인 줄 알았으나 ... 생각보다 많이 헤매었다.

주어진 N을 만족하는 가장 큰 수를 찾을때까지 값을 줄여가며 완전 탐색을 한다는 풀이가 있어서 그대로 해봤다.

입력예제대로 100을 예시로 들어보면,

100부터 1씩 감소하며 for문을 도는데, 

일의자리가 4나 7일경우 다시 10을 나눠서 그 다음 자리도 4나 7인지 판별한다.

만약 num이 0이 될때까지 4나 7로 나누어떨어진다면 그 수가 조건을 만족하는 최댓값이 된다.

100 -> 99 -> 98 -> 97

97 % 10 == 7  ---> num /= 10 (num = 9)

9%10 == 9 이므로, while문을 빠져나오고, 다음 for문을 진행하게 된다.

 

 

다른 풀이들(큐 , 재귀)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String tmp = in.readLine();
		int num = Integer.parseInt(tmp);
		Queue<Integer> q = new LinkedList<Integer>();
		int ans = 0;
		if (num >= 4) {
			q.add(4);
			ans = 4;
		}
		if (num >= 7) {
			q.add(7);
			ans = 7;
		}
		while (!q.isEmpty()) {
			int tmp1 = q.peek();
			q.poll();
			tmp1 *= 10;
			if (tmp1 + 4 <= num) {
				ans = tmp1 + 4;
				q.add(ans);
			}
			if (tmp1 + 7 <= num) {
				ans = tmp1 + 7;
				q.add(ans);
			}
		}
		System.out.println(ans);
	}

}

 

 

import java.util.Scanner;
public class Main {
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        System.out.println(DFS(0));
    }

    static int DFS(int number) {
        int value=number;
        if(number*10+4 <=N)
            value = DFS(number*10+4);
        if(number*10+7 <=N)
            value = Math.max(value, DFS(number*10+7));
        return value;
    }
}

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int result;
	
	static void DFS(int number, int N) {
		if (number > N) return;
		result = Math.max(result, number);
		DFS(number*10 + 4 , N);
		DFS(number*10 + 7 , N);
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		DFS(4,N);
		DFS(7,N);
		
		System.out.println(result);
	}
}

재귀 코드는 봐도 이해가 안되는데 저렇게 재귀적으로 짜려면 얼마나 더 연습해야할까 .............