프로그래머스 숫자카드나누기 (Java)

배인성·2022년 12월 17일
1

프로그래머스

목록 보기
37/55

링크

문제 링크

문제 설명

제한 사항

입출력 예

입출력 예 설명

풀이

  1. 문제를 요약하자면 우선 A배열과 B배열이 있다.
    1-1 A배열에 적힌 숫자를 모두 나눌 수 있는 숫자(최대공약수 공약수)가 존재하면
    1-2 그 숫자는 B배열에서는 아무런 숫자와도 나누어 떨어지면 안된다.
    1-3 위 두개를 만족하는 숫자들 중 가장 큰 수를 리턴하자
  2. 1의 과정을 철수->영희, 영희->철수로 각각 구해서 더 큰 숫자를 최종적으로 리턴하자

이 문제는 지나가다가 프로그래머스에서 한글명으로 변수를 선언하면 그게 될까? 라는 생각이 갑자기 떠올라서 (철수 영희 보고 그랬나..?) 풀어보았다.

문제 핵심은 1-1에 적어놨는데, 최대공약수만 구해서 되는게 아니라 최대공약수의 약수들 모두 로직에 대입해야한다는 것이다.

이거때문에 두번 풀었는데, 나는 뭔가 각 배열을 정렬해서 배열[0]의(최솟값) 약수들을 구해서 GCD인지 따지고 풀었는데 이건 시간적인 비효율을 초래하는 것 같다.

뭔가 바보같다.. 처음에 있던 getGCD를 지우고 저렇게 풀었는데 ㅋㅋㅋ

문제 읽으면서 느낀건데 모든 숫자의 약수가 될 수 있는 1에 대해서는 아무런 언급이 없다는건 조금 아쉬웠다. (눈치껏 피해가는 암묵적인 예외 느낌)

import java.util.*;
class Solution {
    public List<Integer> get_div(int a) {
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= Math.sqrt(a); i++) {
            if(a % i == 0) {
                arr.add(i);
                arr.add(a / i);
            }
        }
        return arr;
    }
    public int problem(int[] arr1, int[] arr2) {
        List<Integer> div = get_div(arr1[0]);
        Collections.sort(div, Collections.reverseOrder());
        int i, j;
        boolean GCD;
        for(i = 0; i < div.size() - 1; i++) {
            GCD = false;
            int num = div.get(i); //현재 숫자
            for(j = 0; j < arr1.length; j++) {
                if(arr1[j] % num != 0)
                {
                    break;
                }
            }
            if(j == arr1.length)
            {
                GCD = true;                
            }
            if(GCD) {
                for(j = 0; j < arr2.length; j++) {
                    if(arr2[j] % num == 0)
                    {
                        break;
                    }
                }
                if(j == arr2.length)
                    return num;
            }
        }
        return 0;
    }
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int 철수;
        int 영희;
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        철수 = problem(arrayA, arrayB);
        영희 = problem(arrayB, arrayA);
        answer = 철수 > 영희 ? 철수 : 영희;
        return answer;
    }
}
profile
부지런히 살자!!

0개의 댓글