[Greedy] Softeer(소프티어) level 2 연탄의 크기 java 풀이

https://softeer.ai/practice/7628

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제 풀이 방법

입력 처리 및 데이터 저장

• 첫 번째 줄에서 정수 n을 입력받습니다. 이는 집의 수를 나타냅니다.
• 두 번째 줄에서 n개의 정수를 입력받아 house 배열에 저장합니다. 이 배열은 각 집의 특정 값을 나타냅니다.
• 입력받은 house 배열을 오름차순으로 정렬합니다.

가능한 난로 반지름 탐색 및 계산

• 변수 answer를 0으로 초기화합니다. 이는 가장 많은 집이 공유할 수 있는 난로 반지름을 찾기 위한 변수입니다.
• 난로의 가능한 반지름을 2부터 가장 큰 집의 값 (house[n - 1])까지 반복합니다:
  1. 각 난로 반지름 j에 대해 변수 current를 0으로 초기화합니다. 이는 현재 반지름으로 난로를 공유할 수 있는 집의 수를 세기 위한 변수입니다.
  2. 모든 집에 대해 반복하면서 (k를 0부터 n-1까지): 만약 house[k] % j == 0이면, 즉 집의 값이 난로 반지름 j로 나누어 떨어진다면 current를 1 증가시킵니다.
  3. 현재 current 값이 기존의 최대값 answer보다 크다면, answer를 current로 업데이트합니다.

결과 출력

• 모든 가능한 난로 반지름에 대한 검사가 끝나면, 최종적으로 가장 많은 집이 공유할 수 있는 난로 반지름에 해당하는 집의 수 answer를 출력합니다.

핵심 아이디어

• 공통 난로 반지름 찾기: 각 집의 값에 대해 공통으로 나누어 떨어지는 난로 반지름을 찾습니다. 이는 집들이 동일한 난로 반지름을 사용할 수 있는지를 판단하는 기준이 됩니다.
• 최대 집의 수 계산: 가능한 모든 난로 반지름에 대해 나누어 떨어지는 집의 수를 계산하고, 그 중 가장 큰 값을 선택하여 answer에 저장합니다.

코드

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

public class Main {

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

        int n = Integer.parseInt(st.nextToken());
        int[] house = new int[n];
        st = new StringTokenizer(in.readLine());
        for(int i = 0; i < n; i++){
            house[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(house);

        int answer = 0;
        int current;
        for(int j = 2; j <= house[n - 1]; j++){
            current = 0;
            for(int k = 0; k < n; k++){
                if(house[k] % j == 0){
                    current++;
                }
            }
            if(current > answer){
                answer = current;
            }
        }
        System.out.println(answer);
    }
}