[softeer] 7628

문제

 

 

 

메모리 제약

 

 

입/출력

 

 

문제 분석

(크기순으로 작성되어있다는 가정하에) 작은 수부터 증가하면서, 뒤에있는 값들을 비교해서 배수인지 확인
 - 배수면 가장 큰 개수 선택

 

 

풀이 1

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

public class Main {

    public static void main(String[] args) throws IOException {

        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(inputStreamReader);

        /*
            * (크기순으로 작성되어있다는 가정하에)
            * 작은 수부터 증가하면서, 뒤에있는 값들을 비교해서 배수인지 확인
            *   - 배수면 가장 큰 개수 선택
         */
        int answer = 1;
        String count = bf.readLine();

        // 집 난로 반지름 입력
        int[] homeR = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();

        // 집들을 돌면서 값 체크
        for (int i = 0; i < homeR.length-1; i++) {
            int useCase = 1;
            for (int j = i+1; j < homeR.length; j++) {
                if (homeR[j]%homeR[i]==0) { // 나눠떨어지면 사용가능
                    useCase++;
                }
            }
            answer = Math.max(useCase, answer);
        }

        System.out.println(answer);
    }
}

 

실패

크기순으로 정렬이 되어있지 않은 것 같다는 생각이 들어서 정렬 후 재시도

 

 

풀이 2

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

public class Main {

    public static void main(String[] args) throws IOException {

        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(inputStreamReader);

        /*
            * (크기순으로 작성되어있다는 가정하에)
            * 작은 수부터 증가하면서, 뒤에있는 값들을 비교해서 배수인지 확인
            *   - 배수면 가장 큰 개수 선택
         */
        int answer = 1;
        String count = bf.readLine();

        // 집 난로 반지름 입력
        int[] homeR = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();

        // 오름차순으로 정렬
        for (int i = 1; i < homeR.length; i++) {
            int tmp;
            for (int j = 0; j < i; j++) {
                if (homeR[i] < homeR[j]) {
                    tmp = homeR[j];
                    homeR[j] = homeR[i];
                    homeR[i] = tmp;
                }
            }
        }

        // 집들을 돌면서 값 체크
        for (int i = 0; i < homeR.length-1; i++) {
            int useCase = 1;
            for (int j = i+1; j < homeR.length; j++) {
                if (homeR[j]%homeR[i]==0) { // 나눠떨어지면 사용가능
                    useCase++;
                }
            }
            answer = Math.max(useCase, answer);
        }

        System.out.println(answer);
    }
}

 

 

실패 2

중간에 두문제를 틀렸다.... 

뭘까 하면서 이것저것 테스트를 해보다가 아래와 같은 case를 발견하였다.

 

6, 9, 12

이 경우 가장 가장 작은 수의 배수가 아니라, 3을 반지름으로 잡아야된다.

 

그래서 풀이 방법을 달리 하기로 하였다.

각 수들의 약수를 구하여 가장 많이 나온 약수의 갯수를 연탄의 반지름으로 잡기로 하였다.

(그렇게 계산하면 정렬 할 필요도 사라지므로 불필요한 연산이 줄어든다고 생각)

   - 1은 모든수의 약수이므로, 최종적으로 1은 제외

 

 

풀이

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

public class Main {

    public static void main(String[] args) throws IOException {

        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bf = new BufferedReader(inputStreamReader);

        String count = bf.readLine();
        // 집 난로 반지름 입력
        int[] homeR = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::new).toArray();

        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int i : homeR) {
            int mid = (int) Math.floor(i);
            for (int j = 1; j <= mid; j++) {
                if (i%j==0) {
                    if (counts.containsKey(j)) {
                        counts.put(j, counts.get(j)+1);
                    } else {
                        counts.put(j, 1);
                    }
                }
            }
        }
        counts.remove(1);
        int answer = 0;

        // 값들을 돌면서 가장 값을 추출
        for (int i : counts.values()) {
            if (answer < i) {
                answer = i;
            }
        }
        System.out.println(answer);
    }
}

 

 

 

성공

 

 

링크

https://softeer.ai/practice/7628

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