[BaekJoon] 2877 4와 7

1.  문제 링크

2.  문제

요약

• 4와 7로만 이루어진 수 중에서 K라는 수가 주어졌을 때 K번째 작은 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10^9보다 작거나 같은 수 K가 주어집니다.
• 출력: 첫 번째 줄에 K번째 작은 수를 출력합니다.

3.  소스코드

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

public class Main {
	public String getMinNum(int num) {
		String[] two_cipher = {"44", "47", "74", "77"};
		if(num == 1) {
			return "4";
		} else if(num == 2) {
			return "7";
		} else  if(num > 2 && num <= 6) {
			return two_cipher[num - 3];
		}
		String result = "";
		int copy = num;
		int cipher = 0;
		while(copy > 0) {
			cipher++;
			copy -= Math.pow(2, cipher);
		}
		copy += Math.pow(2, cipher);
		for(int i = cipher; i > 1; i--) {
			if(i == 2) {
				result += two_cipher[copy - 1];
			} else {
				if(copy <= (Math.pow(2, i) / 2)) {
					result += "4";
				} else {
					result += "7";
					copy -= (Math.pow(2, i) / 2);
				}
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getMinNum(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 4와 7로만 이루어진 수는 자리수가 하나 늘어날 때마다 수의 개수는 이전 자리수에서의 수의 개수에 2배가 됩니다.
• 이 때, 각 자리수에서 앞에서부터 반은 가장 큰 자리수가 4이고 뒤에서 반은 가장 큰 자리수가 7입니다.
• 또한 가장 큰 자리수가 4인 수들과 7인 수들에서 n번째 수들은 가장 큰 자리수를 제외하고 나머지 수들이 현재 자리수보다 한 자리수 낮은 수들에서 n번째인 수와 같습니다.
• 예를 들어 29번째로 작은 수를 찾을 때,
• 한 자리수의 수는 2개, 두 자리수의 수는 4개, 세 자리수의 수는 8개, 네 자리수의 수는 16개이므로 29번째로 작은 수는 세 자리수까지의 수의 개수인 14보다는 크고 네 자리수의 수인 30보다 작으므로 네 자리수가 됩니다.
• 또한 29는 14 + (16 / 2)보다 큰 수이므로 네 자리수 수 중에서 뒤에서 반에 속하니 앞자리가 7이 됩니다.
• 29번째 수는 네 자리수 중에서 15번째에 속하는데 앞자리가 7인 수들 중에서는 7번째에 속하므로 이는 세 자리수 수 중에서 7번째에 속하는 수가 앞자리 7 뒤에 따라오게 됩니다.
• 세 자리수 중에서 7번째에 속하는 수는 774이기 때문에 29번째로 작은 수는 7774가 됩니다.

1. 주어진 수가 1 또는 2일 때는 한 자리수이기 때문에 1일 때는 4, 2일 때는 7을 출력합니다.
2. 두 자리수 수들은 순서대로 배열에 넣어놓은 후에 입력된 수가 2보다 크고 6보다 작거나 같을 때에는 입력된 수에서 2를 뺀 후에 이를 m이라고 한다면 두 자리수 수들 중에서 m번째 수를 출력합니다.
3. 위 두 경우에 모두 해당하지 않는다면 자리수가 늘어날 때마다 해당 자리수에서의 수의 개수가 2배 늘어난다는 사실을 이용하여 찾으려는 수가 몇 자리인지 확인합니다. 이 때, 입력된 수에서 개수를 빼가면서 찾으려는 수의 자리수에서 몇 번째에 해당하는 수인지도 알아냅니다.
4. 각 자리수에서 앞에서 반은 앞자리가 4, 뒤에서 반은 앞자리가 7인 것을 이용해 앞자리를 구하고 만약 앞자리가 7에 해당한다면 앞자리가 7인 수 중에서 몇 번째에 해당하는지 알기 위해 해당 자리수에 존재하는 수의 개수의 반을 빼줍니다.
5. 4번 과정을 자리수를 하나씩 줄여가며 자리수가 두 자리가 될 때까지 진행합니다.
6. 줄여나가며 앞자리 수를 구하다가 남은 것이 두 자리수가 되면 미리 순서대로 저장해놓은 두 자리수 배열을 이용하여 지금까지 구한 수 뒤에 붙입니다. 이렇게 구한 수가 구하려는 수가 됩니다.