[소프티어] 연탄의 크기(JAVA)

문제

https://softeer.ai/practice/7628

---

풀이(7분)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[101]; // 100까지의 수를 저장

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            for(int j =2; j <= num; j++){ // 약수 체크
                if(num % j == 0){
                    arr[j] += 1;
                }
            }
        }

        int max = 1;

        for(int i = 2; i < 101; i++){
            max = Math.max(max, arr[i]);
        }

        System.out.println(max);
    }
}

---

문제 풀이 전략

 

1. 모든 수의 약수 체크

• 모든 수의 약수가 어떤 것이 있는지 체크한다.
• 이 중 약수로 체크된 것이 가장 많은 수를 확인한다.

이렇게 될 경우 n = 100, k = 100인 경우 최대 O(n^4)의 시간 복잡도를 가질 수 있다.

이 문제의 경우 범위가 넓지 않아 해결 가능하다.

사실 좋은 풀이라고 할 수는 없지만, 문제에 적합한 간단한 풀이를 찾는 것도 중요한 능력이라고 생각한다.

 

범위가 넓은 경우에 대해서는 어떻게 하면 좋을까?

굳이 모든 수에 대해 체크하지 말고 최댓값까지의 소수만 체크한 뒤에 이에 대하여 검사를 진행하고, 소수의 배수에 대해서만 체크해 가는 방식이 있을 것 같다.

이 경우에도 더욱 효율적으로 진행하기 위하여 제곱근의 범위까지만 약수를 탐색하는 방향으로 진행하면 될 것 같다.