백준(BOJ) 1527 : 금민수의 개수 (자바, 파이썬)

 

1527번: 금민수의 개수

설계

• 주어진 범위 내에서 "금민수"를 찾는 문제를 해결
  • 금민수란 숫자 4와 7로만 이루어진 숫자를 의미. 예를 들어, 4, 7, 47 등은 금민수.
  • 모든 수를 검사 : 순회하며 주어진 숫자가 금민수인지 판별. 숫자를 10으로 나눈 나머지가 4 또는 7이 아닐 경우, 금민수가 아님.
  • 백트래킹을 통한 금민수 생성 : 재귀적으로 금민수를 생성. 시작 숫자로 4와 7을 사용하고, 각 단계에서 숫자의 끝에 4 또는 7을 추가하여 새로운 금민수를 생성
• 첫 번째 방법 (모든 수를 검사)
  • 이 방법은 A에서 B까지 모든 숫자를 순회하며 금민수인지 확인.
  • 시간 복잡도는 O(N). 여기서 N은 B - A의 범위를 의미.
  • 숫자가 커질수록 계산 시간이 급격히 증가.
• 두 번째 방법 (백트래킹을 이용한 금민수 생성)
  • 이 방법은 백트래킹을 이용하여 금민수를 직접 생성.
  • 시간 복잡도는 금민수의 개수에 비례함. 따라서 O(1)에서 O(2^N) 사이.
  • 금민수의 범위가 작고, 생성해야 하는 금민수의 수가 적을 때 빠른 계산이 가능.
• 두 번째 방법이 첫 번째 방법보다 일반적으로 효율적. 특히 금민수의 범위가 넓고, 금민수의 개수가 상대적으로 적을 때 더욱 그러함. 첫 번째 방법은 간단하지만, 숫자 범위가 넓어질수록 계산 시간이 급증하는 단점이 있음...

구현

코드

자바(Java)

// package boj1527; // 패키지 선언

import java.util.Scanner; // Scanner 클래스 임포트

public class Main {
    static int A, B, count; // 전역 변수 선언: 시작 범위 A, 끝 범위 B, 금민수의 개수 count

    // 메인 메소드
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 사용자 입력을 받기 위한 Scanner 객체 생성
        A = sc.nextInt(); // 시작 범위 A 입력 받기
        B = sc.nextInt(); // 끝 범위 B 입력 받기
        sc.close(); // Scanner 객체 닫기

        // 1번 방법: A와 B 사이의 모든 수를 순회하며 금민수 여부 확인
        // System.out.println("1. A와 B 사이의 모든 수를 검사하는 방법");
        // count = 0;
        // for (int i = A; i <= B; i++) {
        //     if (isGMS(i)) { // i가 금민수인지 확인
        //         System.out.println(i + " is GMS");
        //         count++;
        //     }
        // }
        // System.out.println(count);

        // 2번 방법: 백트래킹을 사용하여 금민수 생성
        // System.out.println("2. 순열을 통한 백트래킹으로 미리 금민수를 생성하는 방법");
        count = 0;
        generateGMS(4); // 4로 시작하는 금민수 생성
        generateGMS(7); // 7로 시작하는 금민수 생성
        System.out.println(count);
    }

    // 금민수인지 확인하는 메서드
    public static boolean isGMS(int num) {
        while (num > 0) {
            int remain = num % 10; // 마지막 자리 수 확인
            if (remain != 4 && remain != 7) { // 4 또는 7이 아니면 false 반환
                return false;
            }
            num /= 10; // 다음 자리 수 확인을 위해 10으로 나눔
        }
        return true; // 모든 자리 수가 4 또는 7이면 true 반환
    }

    // 백트래킹을 사용하여 금민수를 생성하는 메서드
    public static void generateGMS(long num) {
        if (num > B) { // 생성된 숫자가 B를 초과하면 더 이상 진행하지 않음
            return;
        }
        if (num >= A) { // 생성된 숫자가 A 이상이면 금민수로 간주
            System.out.println(num + " is GMS");
            count++;
        }
        generateGMS(num * 10 + 4); // 다음 숫자를 생성하기 위해 4를 추가
        generateGMS(num * 10 + 7); // 다음 숫자를 생성하기 위해 7을 추가
    }
}

파이썬(Python)

# 카드 합 중 최댓값을 찾는 함수
def is_gms(num):
    # 금민수인지 확인하는 함수
    while num > 0:
        remain = num % 10  # 마지막 자리 수 확인
        if remain != 4 and remain != 7:  # 4 또는 7이 아니면 False 반환
            return False
        num //= 10  # 다음 자리 수 확인을 위해 10으로 나눔
    return True  # 모든 자리 수가 4 또는 7이면 True 반환

def generate_gms(num, A, B, count):
    # 백트래킹을 사용하여 금민수를 생성하는 함수
    if num > B:  # 생성된 숫자가 B를 초과하면 더 이상 진행하지 않음
        return count
    if num >= A:  # 생성된 숫자가 A 이상이면 금민수로 간주
        # print(f"{num} is GMS")
        count += 1
    count = generate_gms(num * 10 + 4, A, B, count)  # 4를 추가하여 금민수 생성
    count = generate_gms(num * 10 + 7, A, B, count)  # 7을 추가하여 금민수 생성
    return count

# 사용자 입력 받기
A, B = map(int, input().split())
# 카운트
count = 0

'''
# 1번 방법: A와 B 사이의 모든 수를 순회하며 금민수 여부 확인
print("1. A와 B 사이의 모든 수를 검사하는 방법")
for i in range(A, B + 1):
    if is_gms(i):  # i가 금민수인지 확인
        print(f"{i} is GMS")
        count += 1
print(count)
'''

# 2번 방법: 백트래킹을 사용하여 금민수 생성
# print("2. 순열을 통한 백트래킹으로 미리 금민수를 생성하는 방법")
count = generate_gms(4, A, B, 0)  # 4로 시작하는 금민수 생성
count = generate_gms(7, A, B, count)  # 7로 시작하는 금민수 생성
print(count)