[백준] 4와 7 (구현+수학)

문제 소개

4와 7 - 백준 2877번 문제를 정리합니다.
이 문제는 4와 7로만 이루어진 수 중 K번째 작은 수를 출력하는 이진 + 수학적 규칙 문제입니다.

문제 링크: 4와 7 - 백준 2877번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 4와 7로만 이루어진 수는 2진수처럼 구성 → 자리수 N이면 2ⁿ개의 수 생성 가능
2. 자리수마다 몇 개의 수가 있는지 누적합을 구해 K번째 수의 자리수를 결정
3. 해당 자리수 내에서의 인덱스를 2진수로 변환 후 → '0'을 4, '1'을 7로 치환

---

해결 과정 및 코드

핵심 아이디어

1. 4, 7, 44, 47, 74, 77 … 이런 식으로 4와 7로만 이루어진 모든 수는 자리수가 증가할수록 2진수처럼 구성됨

4, 7 / 44, 47, 74, 77 / 444, 447, 474, 477, 744
0, 1 / 00, 01, 10, 11 / 000, 001, 010, 011, 100 

1. 자리수 N이면 2ⁿ개의 수 생성 가능 → K가 어느 자리수의 수에 속하는지 먼저 계산
2. 자리수 확정 후 그 자리수에서 몇 번째인지 계산 → 해당 인덱스를 2진수로 변환
3. 2진수의 각 자리를 '0' → '4', '1' → '7'로 치환하여 최종 결과 생성

코드

시간 복잡도 : O(logK)
: 반복문이 length를 기준으로 조건 설정됨 length는 최대 log₂K까지 증가할 수 있기에 자리수 판별 과정의 시간복잡도는 O(logK)

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		int K = read();  // 입력값 K
		System.out.println(findKthLuckyNumber(K));  // 결과 출력
	}

	public static String findKthLuckyNumber(long K) {
		int length = 1;
		long count = 0;

		// Step 1: 자리수 결정
		while (true) {
			long numAtLength = 1L << length; // 2^length
			if (count + numAtLength >= K) break;
			count += numAtLength;
			length++;
		}
		
		// 4, 7 / 44, 47, 74, 77 / 444, 447, 474, 477, 744
		// 0, 1 / 00, 01, 10, 11 / 000, 001, 010, 011, 100 
		// Step 2: 해당 자리수에서 몇 번째인지 (0-based index)
		long idx = K - count - 1;

		// Step 3: 2진수로 변환 후 자릿수 맞추기 (앞에 0 채움)
		StringBuilder binary = new StringBuilder(Long.toBinaryString(idx));
		while (binary.length() < length) {
			binary.insert(0, '0');
		}

		// Step 4: 0 -> 4, 1 -> 7로 매핑
		StringBuilder result = new StringBuilder();
		for (int i = 0; i < binary.length(); i++) {
			result.append(binary.charAt(i) == '0' ? '4' : '7');
		}

		return result.toString();
	}

	// 빠른 입력 처리
	public static int read() throws Exception {
		int n = System.in.read() & 15, cur;
		while ((cur = System.in.read()) > 32) {
			n = (n << 3) + (n << 1) + (cur & 15);
		}
		return n;
	}
}