[Gold V] 4와 7 - 2877

문제 링크

성능 요약

메모리: 14252 KB, 시간: 104 ms

분류

구현, 수학

문제 설명

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

입력

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

출력

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

풀이과정

1자리의 47수: 2		# 4, 7
2자리의 47수: 4		# 44, 47, 74, 77
3자리의 47수: 8		# 444, 447, 474, 477, 744, 747, 774, 777
4자리의 47수: 16	# 4444, 4447, 4474, 4477, 4744, 4747, 4774, 4777,
			# 7444, 7447, 7474, 7477, 7744, 7747, 7774, 7777

bfs로 풀려고 했는데 K(1 ≤ K ≤ 10⁹)범위로 큐에 모든 숫자를 넣는 방식은 메모리 초과를 초래합니다.

아래 코드는 잘못된 범위와 시간을 고려하지 않는 코드입니다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long k = Long.parseLong(br.readLine());  // K번째 숫자

        Queue<String> que = new LinkedList<>();
        que.add("4");
        que.add("7");

        long count = 0;

        while(!que.isEmpty()) {
            String current = que.poll();
            count++;
            
            // K번째 숫자를 찾으면 종료
            if (count == k) {
                System.out.println(current);
                return;
            }
            
            // "4"와 "7"을 이어 붙인 새로운 숫자들을 큐에 추가
            que.add(current + "4");
            que.add(current + "7");
        }
    }
}

해결 방법

4와 7을 0과 1로 바꾸어 2진수와 같이 생각합니다.
입력한 수에 1을 더한 뒤 2진수로 바꾸면 규칙을 찾을 수 있습니다.
n번째 수를 찾으려면 n+1을 이진수로 바꾸고 가장 앞자리를 생략합니다.

❌ 0부터 시작하면 어떻게 될까?

0	0	4	❌ (없어야 함)
1	1	7	❌ (4여야 함!)
2	10	4 7	❌ (7여야 함!)
3	11	7 7	❌ (44여야 함!)

❌ +1을 하지 않고 변환해볼까?

1	1	7	❌ (4여야 함)
2	10	4 7	❌ (7여야 함)
3	11	7 7	❌ (44여야 함)

✅ +1을 하고 변환하면?

1	2	10	4 7	4 ✅
2	3	11	7 7	7 ✅
3	4	100	4 4 4	44 ✅

정답 코드

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String s = Integer.toBinaryString(Integer.parseInt(br.readLine())+1).replace('0','4').replace('1', '7');
		for(int i=1;i<s.length();i++) 
			bw.write(s.charAt(i));
		
		bw.flush();
		bw.close();
	}
}