[프로그래머스][C++] 숫자 카드 나누기
숫자 카드 나누기
문제 링크
분석
arrayA의 모든 요소를 나눌 수 있어야 하며, arrayB의 어떤 요소도 나눌 수 없는 x를 구해야합니다.
또는 arrayB의 모든 요소를 나눌 수 있어야 하며, arrayA의 어떤 요소도 나눌 수 없는 x를 구해야합니다.
이 두가지 조건 중 하나라도 만족하는 x값 중에서 가장 큰 값을 구해야합니다.
어떤 수가 배열의 모든 수를 나눌 수 있다라는 것은 그 수가 배열의 최대공약수라는 것을 의미합니다.
각 배열의 최대공약수를 구하고, 다른 배열의 어떤 요소도 나눌 수 없는지 확인해주어야합니다.
다른 배열을 나눌 수 없는 최대공약수 중 가장 큰 값을 반환하면 됩니다.
만약 조건을 만족하는 x가 없다면, 0을 반환해야합니다.
풀이
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// 배열의 최대공약수를 구합니다.
int getGCD(const vector<int>& arr)
{
int result = arr[0];
for (int i = 1; i < arr.size(); ++i)
{
// 이전까지의 최대공약수와 현재 요소의 최대공약수를 계산합니다.
result = gcd(result, arr[i]);
}
return result;
}
// 주어진 수의 약수들을 구합니다.
vector<int> getDivisors(int num)
{
vector<int> divisors;
// 제곱근까지만 반복해서 반복 횟수를 줄입니다.
for (int i = 1; i * i <= num; ++i)
{
// 약수인 경우
if (num % i == 0)
{
// 크기가 작은 약수를 저장
divisors.push_back(i);
// 제곱수가 아닌 경우 대응되는 큰 약수를 저장합니다.
if (i != num / i)
{
divisors.push_back(num / i);
}
}
}
// 큰 수부터 검사하기 위해 내림차순으로 정렬
sort(divisors.rbegin(), divisors.rend());
return divisors;
}
// 약수가 배열의 모든 요소를 나눌 수 없는지 확인합니다.
bool isValid(int x, const vector<int>& arr)
{
for (int a : arr)
{
// 배열의 요소 중 1개라도 나눌 수 있는 경우
if (a % x == 0)
{
return false;
}
}
// 나눌 수 없는 경우
return true;
}
int solution(vector<int> arrayA, vector<int> arrayB) {
int answer = 0;
// 두 배열의 최대공약수를 구합니다.
int gcdA = getGCD(arrayA);
int gcdB = getGCD(arrayB);
// arrayA의 최대공약수로 구한 약수들 중에서 arrayB의 요소를 나눌 수 없는 가장 큰 수를 찾습니다.
vector<int> divisorsA = getDivisors(gcdA);
for (int element : divisorsA)
{
// arrayB의 요소를 나눌 수 없는 경우
if (isValid(element, arrayB))
{
// 최대값 갱신
answer = max(answer, element);
// 내림차순으로 확인하기 때문에 나머지 값은 확인할 필요 없습니다.
break;
}
}
// arrayB의 최대공약수로 구한 약수들 중에서 arrayA의 요소를 나눌 수 없는 가장 큰 수를 찾습니다.
vector<int> divisorsB = getDivisors(gcdB);
for (int element : divisorsB)
{
// arrayA의 요소를 나눌 수 없는 경우
if (isValid(element, arrayA))
{
// 최대값 갱신
answer = max(answer, element);
// 내림차순으로 확인하기 때문에 나머지 값은 확인할 필요 없습니다.
break;
}
}
return answer;
}
성능 요약
시간 복잡도는 $O(n \ log \ m + \sqrt{d} \times n)$입니다.
- 최대공약수를 구하는 함수 $O(n \ log \ m)$
n은 배열 크기,m은 배열 내 최대 수
- 최대공약수의 약수를 구하는 함수 $O(\sqrt{d})$
d는 최대공약수의 크기
- 모든 약수가 배열의 모든 요소를 나눌 수 있는지 확인하는 반복문 $O(\sqrt{d} \times n)$
- 약수가 배열의 모든 요소를 나눌 수 없는지 확인하는 함수 $O(n)$
- $O(n \ log \ m) + O(n \ log \ m) + O(\sqrt{d}) + O(\sqrt{d}) + O(\sqrt{d} \times n) + O(\sqrt{d} \times n)$
공간 복잡도는 $O(\sqrt{d})$입니다.
- 최대공약수의 약수를 저장한
vector<int> divisorsA,vector<int> divisorsB$O(\sqrt{d}) + O(\sqrt{d})$
테스트 1 〉 통과 (0.03ms, 4.15MB)
테스트 2 〉 통과 (0.09ms, 4.14MB)
테스트 3 〉 통과 (0.02ms, 4.21MB)
테스트 4 〉 통과 (0.96ms, 5.75MB)
테스트 5 〉 통과 (0.18ms, 4.03MB)
테스트 6 〉 통과 (0.39ms, 4.56MB)
테스트 7 〉 통과 (0.05ms, 3.77MB)
테스트 8 〉 통과 (0.05ms, 3.73MB)
테스트 9 〉 통과 (0.18ms, 4.29MB)
테스트 10 〉 통과 (0.02ms, 4.16MB)
테스트 11 〉 통과 (16.14ms, 38.5MB)
테스트 12 〉 통과 (14.38ms, 38.5MB)
테스트 13 〉 통과 (14.87ms, 38.5MB)
테스트 14 〉 통과 (13.63ms, 38.5MB)
테스트 15 〉 통과 (13.52ms, 38.5MB)
테스트 16 〉 통과 (13.54ms, 38.5MB)
테스트 17 〉 통과 (13.15ms, 38.5MB)
테스트 18 〉 통과 (13.69ms, 38.5MB)
테스트 19 〉 통과 (0.01ms, 4.13MB)
테스트 20 〉 통과 (0.01ms, 4.21MB)
테스트 21 〉 통과 (0.01ms, 4.13MB)
테스트 22 〉 통과 (0.01ms, 4.19MB)
테스트 23 〉 통과 (0.01ms, 4.19MB)
테스트 24 〉 통과 (0.01ms, 4.16MB)
테스트 25 〉 통과 (0.01ms, 4.13MB)
테스트 26 〉 통과 (0.01ms, 4.16MB)
테스트 27 〉 통과 (0.01ms, 4.19MB)
테스트 28 〉 통과 (0.01ms, 4.12MB)
테스트 29 〉 통과 (0.01ms, 4.14MB)
테스트 30 〉 통과 (0.01ms, 4.14MB)
테스트 31 〉 통과 (0.01ms, 4.16MB)
테스트 32 〉 통과 (0.01ms, 4.2MB)
테스트 33 〉 통과 (0.01ms, 4.13MB)
테스트 34 〉 통과 (0.01ms, 3.67MB)
테스트 35 〉 통과 (0.01ms, 3.66MB)
테스트 36 〉 통과 (0.01ms, 4.2MB)
댓글남기기