[백준] 4와 7 : 2877: 구현, 이진 수 - Java

1. 문제

 

 

요약

4와 7을 이용해서 K 번째 작은 수 만들기

 

 

2. 접근

작은 수를 차례로 써보면 

 

4,

7,

44,

47,

77,

444,

447,

474

...

이다.

 

숫자만 다를 뿐 두 개의 수로 표현한다는 점에서 이진수를 표현하는 방법과 유사하다.

k번째로 작은 수	0과 1로 표기
4	0
7	1
44	00
47	01
77	11
444	000
447	001
474	010

 

이 방법까지 떠올리면 반은 온거다.

 

하지만 이진 수랑 다른 점이 있다. 바로 맨 앞 bit에 0이 온다는 것이다. 최대한 이진수랑 연관시켜서 방법을 찾아야 한다. 이진수를 쭉 써보자

 

k번째로 작은 수	0과 1로 표기	이진수
4	0	1
7	1	10
44	00	11
47	01	100
77	11	101
444	000	110
447	001	111

 

규칙이 있다. 잘 보면 k번째 작은 수는 k+1를 이진 수로 표현한 것에서 맨 앞 비트를 없애면 똑같다.

예를 들면, 4번쨰로 작은 수는 `47`이다. 47을 0과 1로 표현하면 `01`이고, 이는 `5(101)`에서 맨 앞 비트인 1를 뺴준 거랑 같다.

 

그러므로 K+1번째의 이진 수를 구한다음, 맨 앞 비트를 빼준 후 0은 4로, 1은 7로 변환 해주면 된다.

 

 

3. 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main{

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int K = Integer.parseInt(br.readLine());

        List<Integer> bits = new ArrayList<>();
        intToBinary(K+1, bits);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<bits.size(); i++){
            sb.append(bits.get(i)==0? "4" : "7");
        }
        System.out.println(sb.toString());
    }


    public static void intToBinary(int n, List<Integer> bits){
        if (n== 1 || n == 0){
            bits.add(n);
            return;
        }

        intToBinary(n/2, bits);
        bits.add(n%2);
    }

}