문제 풀이 날짜: 2025-08-16
💡Github URL
쉬운 문제라서 나머지는 최대한 간단하게 적었음.
다만 '시간복잡도' 분석에서 기록하고자 하는게 있어 거기를 중점적으로 적었음.
💡알고리즘 설계
비트마스킹을 통해 0~9까지 모든 숫자가 1번 이상 등장했는지 확인
💡코드
메모리: 59,520 KB, 시간: 75 ms, 코드길이: 321 Bytes
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
static BufferedReader br;
static StringBuilder sb;
static int end;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
end = (1 << 10) - 1;
for(int tc=1; tc<T+1; tc++){
int N = Integer.parseInt(br.readLine());
int tmp = 0;
int cnt = 1;
while(true){
char[] ch = String.valueOf(N * cnt).toCharArray();
for(int i=0; i<ch.length; i++) {
int num = ch[i] - '0';
tmp = tmp | (1 << num);
}
if(tmp == end) break;
cnt ++;
}
sb.append("#").append(tc).append(" ").append(cnt * N).append("\n");
}
System.out.println(sb);
}
}💡시간복잡도
약 100
Big-O 표기법 말고 이렇게 작성하는 것은 잘못된 방식으로 보일 수 있음.
그러나 풀이를 본다면, while(true)를 통해 무한 반복하다가, 조건을 만족할 때 break로 종료하기 때문에 일반적인 코드 분석을 통해 Big-O 표기법으로 분석할 수 없음.
이 문제의 경우 다른 방식을 통해 시간 복잡도를 예측할 수 있음.
시간 복잡도 약 100라는 것은 어떠한 경우에도, 100번 센다면 0~9까지 모든 숫자를 다 볼 수 있다는 의미.
대표적인 예시 상황으로 N=2를 본다면 다음과 같음.
2, 4, 6, 8, 0 처럼 일의 자리에서는 짝수만 나올 수 있음.
때문에 홀수(1, 3, 5, 7, 9)는 자릿수의 올림을 통해 십의 자리 이상에서만 볼 수 있음.
ex) 10, 20, 30, 40, ...
이처럼, 자릿수의 올림을 통해서는 1~9까지 모든 숫자가 나올 수 있음.
그러나 여기서 볼 점은 자릿수의 올림은 무조건 1씩 올라간다는 점.
N = 99999 처럼 매우 큰 수라도 처음으로 자릿수의 올림이 발생하는 상황은 2N = 199998임. 어떠한 상황에서도, 자릿수의 올림이 2 이상 발생할 수 없음.
일반화 한다면, 주어진 N이 처음에 K 자리수라고 한다면, 100N은 반드시 K+2 자리수임. 그렇다는 것은 N ~ 100N 사이의 자릿수의 올림이 발생하는 과정에서 K+1 자리수에서 1 ~ 9가 반드시 나온다는 뜻. 추가적으로 0은 100N에서 K+1 자리수에서 나올 수 있음.
따라서, N에 상관 없이 모든 수는 N ~ 100N 까지 중에서 0부터 9까지 숫자가 반드시 1회 이상 출현한다고 일반화 할 수 있음.
💡 기억할정보
이렇게 코드 분석이 아닌, 문제 상황 분석을 통한 시간 분석도 예측도 알아둬야 함.
이러한 방식을 통해 while(true) 같은 무한 반복도 최악의 상황을 예측하여 시간 복잡도를 분석할 수 있어짐.
