[BaekJoon] 2877 4와 7
1. 문제 링크
https://www.acmicpc.net/problem/28772. 문제
요약
- 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 또는 2일 때는 한 자리수이기 때문에 1일 때는 4, 2일 때는 7을 출력합니다.
- 두 자리수 수들은 순서대로 배열에 넣어놓은 후에 입력된 수가 2보다 크고 6보다 작거나 같을 때에는 입력된 수에서 2를 뺀 후에 이를 m이라고 한다면 두 자리수 수들 중에서 m번째 수를 출력합니다.
- 위 두 경우에 모두 해당하지 않는다면 자리수가 늘어날 때마다 해당 자리수에서의 수의 개수가 2배 늘어난다는 사실을 이용하여 찾으려는 수가 몇 자리인지 확인합니다. 이 때, 입력된 수에서 개수를 빼가면서 찾으려는 수의 자리수에서 몇 번째에 해당하는 수인지도 알아냅니다.
- 각 자리수에서 앞에서 반은 앞자리가 4, 뒤에서 반은 앞자리가 7인 것을 이용해 앞자리를 구하고 만약 앞자리가 7에 해당한다면 앞자리가 7인 수 중에서 몇 번째에 해당하는지 알기 위해 해당 자리수에 존재하는 수의 개수의 반을 빼줍니다.
- 4번 과정을 자리수를 하나씩 줄여가며 자리수가 두 자리가 될 때까지 진행합니다.
- 줄여나가며 앞자리 수를 구하다가 남은 것이 두 자리수가 되면 미리 순서대로 저장해놓은 두 자리수 배열을 이용하여 지금까지 구한 수 뒤에 붙입니다. 이렇게 구한 수가 구하려는 수가 됩니다.
Author And Source
이 문제에 관하여([BaekJoon] 2877 4와 7), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taeho97/BaekJoon-2877-4와-7저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)