[실버4] BOJ1065 한수

요구사항

1부터 N까지의 한수를 출력하는 프로그램을 작성하시오.

문제분석

• 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.
• 시간제한 = 2초 = 2억번의 연산
• 시간복잡도 분석
  → 1부터 N까지 순회하면서 각 자리수를 나열해 숫자간에 공차가 일정한지 확인하기 때문에? = O(N)?? ❌ 
  외부 루프: 1부터 N까지 N번 순회
  내부 작업 (한수 검사): 각 숫자 x에 대해 실행되는 작업은 '자릿수 분리 및 검사'
  총 연산 횟수 = 외부 순회 횟수 x 내부 작업 연산 횟수 = N X C(상수) = O(N)

손으로 풀기

1. 1부터 N까지 순회한다
2. 숫자를 나열한다.
3. 나열한 수의 ‘공차’ 가 같은지 확인한다. → 맞다면 count를 증가시킨다.

Sudo code

    입력 N
    count = 0

    // 1. 99 이하의 수 처리 (상수 시간 처리)
    if (N < 100) {
        count = N;
    } else {
        count = 99; // 1부터 99까지는 무조건 한수이므로 99개로 시작
        
        // 2. 100부터 N까지 반복하며 한수 검사 (O(N))
        for (i = 100 to N) {
            
            // X의 각 자릿수를 분리
            백의자리 = i / 100
            십의자리 = (i / 10) % 10
            일의자리 = i % 10

            // 3. 공차 비교
            // (십의자리 - 백의자리) == (일의자리 - 십의자리)
            if ((백의자리 - 십의자리) == (십의자리 - 일의자리) ) {
                count++;
            }
        }
    }

    count 출력

Code

import java.util.Scanner;

public class BOJ1065 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int count = 0;
        sc.close();

        // 1. 99 이하의 수 처리 (O(1) 처리)
        if (N < 100) {
            System.out.println(N);
            // System.exit(0) 대신 return 사용을 권장합니다.
            return; 
        } 
        
        // 2. 100 이상일 경우, 1~99는 이미 한수이므로 99개로 시작
        count = 99;
        
        // N이 1000인 경우 (1000은 한수가 아님), 999까지만 검사합니다.
        // N=1000이 입력된 경우, 루프를 999까지 돌리기 위해 N을 999로 제한합니다.
        int limit = (N == 1000) ? 999 : N;

        // 3. 100부터 N까지 반복하며 한수 검사 (반복 조건 수정: i <= limit)
        for(int i = 100; i <= limit; i++){

            int 백의자리 = i / 100;
            // 💡 십의자리 분리 로직 수정
            int 십의자리 = (i / 10) % 10;
            int 일의자리 = i % 10;

            // 4. 공차 비교
            if((십의자리 - 백의자리) == (일의자리 - 십의자리)) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}