[프로그래머스/JAVA] 코딩테스트 연습 > 연습문제 > 숫자 카드 나누기 (by 다알쥐AI)

[가장먼노드] 코딩테스트 연습 > 연습문제 > 숫자 카드 나누기

 

틱톡라이트 초대링크  https://lite.tiktok.com/t/ZSjqX7SfC/

[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

 

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

---

제한사항

제한사항

• 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
• 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

---

입출력 예

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.

---

[간단설명]

철수 카드 전부 나눌 수 있고, 영희 카드 전부 나눌 수 없는 양의 정수 or 그 반대 경우 중, 최대값 구하기

 

[접근방법]

1. 철수 카드, 영희 카드 모두 오름차순 정렬한다.

2. 각 카드 배열 첫 번째 숫자 중에서, 더 큰 값을 찾는다.(max)

3. max를 기준으로 1씩 감소하면서 나누기 조건을 검사한다.

    3.1. 철수 카드 전부 나눌 수 있고, 영희 카드 전부 나눌 수 없는 숫자 리턴 

    3.2. 영희 카드 전부 나눌 수 있고, 철수 카드 전부 나눌 수 없는 숫자 리턴 

4. 정답이 없으면 0 리턴 

 

[주의사항]

- 카드 원소 범위가 100,000,000 으로 범위가 크기 때문에, 2부터 나누기 검사를 하면 비효율 적이다.

ㄴ> 카드 배열을 미리 정렬해놓고, 첫번째 원소를 나누기 max 값으로 지정하면 범위를 확 줄일 수가 있다.

 

[소스공개]

import java.util.*;
class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        // 철수 카드(arrayA), 영희 카드(arrayB) 오름차순 정렬
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        
        // 첫 번째 카드 중에서 더 큰 숫자를 저장
        // 즉, 양의 정수 a의 최대값 
        int max = Math.max(arrayA[0],arrayB[0]);
       
        // max부터 -1씩 나누기 검사
        for(int i=max;i>1;i--){
            // arrayA로 전부 나눌 수 있고
            // arrayB로 전부 나눌 수 없으면
            if(isDivision(arrayA,i)){
                if(isNotDivision(arrayB,i)) return i;
            }
            // arrayB로 전부 나눌 수 있고
            // arrayA로 전부 나눌 수 없으면
            else if(isDivision(arrayB,i)){
                if(isNotDivision(arrayA,i)) return i;
            }
        }
        // 정답이 없으면 0 리턴
        return 0;
    }
    // 전부 나눌 수 있는지 판별
    public boolean isDivision(int[] arr, int n){
        for(int i=0;i<arr.length;i++){
            if(arr[i]%n!=0) return false;
        }
        return true;
    }
    // 전부 나눌수 없는지 판별
    public boolean isNotDivision(int[] arr, int n){
        for(int i=0;i<arr.length;i++){
            if(arr[i]%n==0) return false;
        }
        return true;
    }
}

 

[실행결과]