반응형

1418번 K-세준수

N까지의 값을 입력받아서 각 수의 소인수분해를 통해 소인수를 받고 해당 소인수의 최댓값을 입력받은 K와 비교해 카운트한 수를 출력

-----

hint

각 소인수를 hashMap에 저장 이후 맥스값 출력

-----

Solution

실행시간 - 3496ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
import java.io.*;
// 1 2 3 4 5 6 7 8 9 10
// 1 2 3 2 5 3 7 2 3 5
class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); 
        int k = Integer.parseInt(br.readLine());
        int[] a = new int[n+1];
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>(n+1);
        
        for(int i = 0; i <= n; i++){
            a[i] = i;
            hs.put(i,0);//해시맵 초기화
        }
        
        //1은 되니까 배제
        for(int i = 2; i <= n; i++){//2부터 n까지의 소인수들을 저장
            int soinsu = a[i];
            for(int j = 2; j <= soinsu; j++){
                while(soinsu % j == 0){ 
                    soinsu /= j;
                    hs.put(i, j);
                }
                // 소인수분해 한 값들중에서 max값을 해당 hs에 집어넣는다.
            }
        }
        
        int count = 0;
        for(int i = 1; i < a.length; i++){
            if(hs.get(i) <= k){
                count++;
            }
        }
        System.out.println(count);
    }
}
cs

직접 무식하게 푼거라 효율이 매우 좋지 않음...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25

+ Recent posts

티스토리툴바