BOJ_2877_4와 7 (Java)

[Gold V] 4와 7 - 2877

문제 링크

성능 요약

메모리: 14284 KB, 시간: 100 ms

분류

구현, 수학

제출 일자

2025년 3월 19일 20:04:13

문제 설명

창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 K(1 ≤ K ≤ 10⁹)가 주어진다.

출력

첫째 줄에 창영이가 좋아하는 숫자 중 K번째 작은 수를 출력한다.

문제 풀이

1. 자릿수별 개수 파악
   • 1자리 숫자: 2개 (4, 7) = 2¹
   • 2자리 숫자: 4개 (44, 47, 74, 77) = 2²
   • 3자리 숫자: 8개 (444, 447, …) = 2³
   • n자리 숫자: 2ⁿ개

2. K번째 숫자의 자릿수 찾기

3. 해당 자릿수 내에서의 위치 계산

4. 이진수 변환
   • 자릿수 내 위치(pos)를 이진수로 표현
   • 0은 4로, 1은 7로 변환

K번째 숫자가 몇 자리 숫자인지 찾고, 해당 자릿수 내에서의 위치를 이진수로 표현한 뒤 4와 7로 변환

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2877_4와7/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        long K = Long.parseLong(br.readLine());

        int digits = 1;
        long sum = 0;

        while(true){
            long cnt = 1L << (digits);

            if(sum + cnt >= K) break;

            sum += cnt;
            digits++;
        }

        long pos = K - sum - 1; // K-sum 번째이므로 인덱스로는 -1

        for(int i=0; i<digits; i++){ // 맨 오른쪽 자릿수부터 숫자찾기, 0이면 작은수 1이면 큰수
            if((pos & (1L << (digits - 1 - i))) == 0) sb.append("4");
            else sb.append("7");
        }
        System.out.println(sb.toString());
        br.close();
    }
}