백준 2877 4와 7 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/2877

2877번: 4와 7

문제

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

입력

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

출력

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

알고리즘 분류

• 수학
• 구현

풀이

단순 구현 문제이다.

우선 자릿수가 증가하는 구간을 생각해 보면

4

7

bound = 2

44

47

74

77

bound = 4

444

447

474

477

744

747

774

777

bound = 8

각각 2의 배수에 해당되는 수만큼 4와 7로 이루어진 숫자를 가지고 있다.

그럼 만약 k가 10이라고 하면 444 ~ 777 범위 내에서만 찾으면 되고 앞에 숫자들과 뒤의 숫자들은 필요 없게 된다.

그럼 이 범위에 맞게 k를 바꾸어 주자.

444 앞에 숫자가 6개 있으니 k는 10-6으로 4가 된다.

이제 bound와 k를 이용해 앞자리 수부터 구해주면 된다.

현재 bound가 8이고 앞에 반절은 4, 뒤 반절은 7이기 때문에 맨 앞자리 수는 4가 된다.

answer = 4??

이제 뒤의 두 자리를 구해야 하기 때문에 bound와 k를 다시 줄여 범위를 조정한다.

bound는 8에서 bound인 4로 바뀌고 k는 bound인 4보다 작기 때문에 냅둔다. 만약에 바뀐 bound (이전 bound의 중간)보다 크다면 바뀐 bound만큼 빼주면 된다.

따라서 bound = 4, k = 4이기 때문에 두 번째 자리는 7이 된다.

answer = 47

마지막으로 bound = 2, k = 2이기 때문에 마지막 자리도 7이 된다.

 

본인은 딱 이정도 규칙만 찾고 풀었는데 조금 더 규칙을 찾아보면 k번째 숫자가 (k+1)을 이진수로 변환한 값을 '1' = 7 , '0' = 4로 치환하면 k번째 숫자를 쉽게 찾을 수 있다. 그럼 아래와 같은 간단한 코드가 가능해진다.

fun main() {
    val k = (readln().toInt() + 1).toString(2)
    val sb = StringBuilder()
    for (i in 1 until k.length) {
        sb.append(if (k[i] == '0') '4' else '7')
    }
    print(sb)
}

출처 : https://www.acmicpc.net/source/46094312

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()) {
    var k = getInt()

    var sum = 0
    var bound = 2
    while (sum < k) {
        sum += bound
        bound *= 2
    }
    bound /= 2
    k -= sum-bound
    val sb = StringBuilder()
    while (bound > 1) {
        bound/=2
        if (k > bound) {
            sb.append('7')
            k-=bound
        }
        else sb.append('4')
    }
    write("$sb")
    close()
}