알고리즘 코드카타 - 119. 숫자 카드 나누기
문제 설명
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.
- 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
- 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 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에는 중복된 원소가 있을 수 있습니다.
입출력 예
arrayA arrayB result [10, 17] [5, 20] 0 [10, 20] [5, 17] 10 [14, 35, 119] [18, 30, 102] 7 입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
입출력 예 #2
- 문제 예시와 같습니다.
입출력 예 #3
- 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.
풀이 코드
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
vector<int> getDivisors(int g)
{
vector<int> result;
for(int i = 1; i*i <= g; i++)
{
if(g % i == 0)
{
result.push_back(i);
if(i != g / i) result.push_back(g/i);
}
}
sort(result.rbegin(), result.rend());
return result;
}
bool IsValid(int x, vector<int>& array)
{
for(int num : array)
{
if(num % x == 0)
{
return false;
}
}
return true;
}
int solution(vector<int> arrayA, vector<int> arrayB) {
int answer = 0;
// 배열에서 최대공약수 뽑기
int ga = arrayA[0], gb = arrayB[0];
for(int a : arrayA)
{
ga = gcd(ga, a);
}
for(int b : arrayB)
{
gb = gcd(gb, b);
}
vector<int> adivisors = getDivisors(ga);
vector<int> bdivisors = getDivisors(gb);
for(auto& cd : adivisors)
{
if(IsValid(cd, arrayB))
{
answer = max(cd, answer);
break;
}
}
for(auto& cd : bdivisors)
{
if(IsValid(cd, arrayA))
{
answer = max(cd,answer);
break;
}
}
return answer;
}- 문제에서 요구하는
양의 정수 a의 조건은 다음과 같다.- 카드에 적힌 모든 숫자를 나눌 수 있다.
- 1번을 만족하는 수 중 가장 큰 수이다.
- 또한 상대가 가진 카드를 하나도 나눌 수 없어야 한다.
1번과 2번 조건을 통해
공약수 혹은 최대공약수라는 것을 알 수 있고, 다른 배열의 원소들을 이 수로 나눠서 나누어 떨어지지 않으면 조건을 만족하는a를 구할 수 있다. gcd()와getDivisors()로 공약수의 집합을 구하고 이를 내림차순 정렬한다.IsValid()는 매개변수로 정수x와 정수배열array를 입력받는데,array를 순회하며x로 나누고, 하나라도 나누어 떨어지면 false, 전부 나누어떨어지지 않으면 true를 반환하는 함수IsValid()를 이용해 가장 큰 공약수부터 상대 배열을 순회한다. 조건이IsValid()이므로, 나누어 떨어지지 않을 때 해당cd를 반환하게 된다.- 문제에서 요구하는 것은 가장 큰 수이므로
answer = max(cd, answer)로 최댓값을 항상 갱신해준다.
개선된 풀이 코드
#include <string>
#include <vector>
#include <numeric>
using namespace std;
bool IsValid(int x, vector<int>& array)
{
for(int num : array)
{
if(num % x == 0)
{
return false;
}
}
return true;
}
int solution(vector<int> arrayA, vector<int> arrayB) {
int answer = 0;
// 배열에서 최대공약수 뽑기
int ga = arrayA[0], gb = arrayB[0];
for(int a : arrayA)
{
ga = gcd(ga, a);
}
for(int b : arrayB)
{
gb = gcd(gb, b);
}
if(IsValid(ga,arrayB)) answer = max(answer, ga);
if(IsValid(gb,arrayA)) answer = max(answer, gb);
return answer;
}
- 사실 공약수의 집합을 구할 것도 없이 바로 최대공약수만으로도 문제 해결이 가능하다.
gcd(arrayA) = 12 일 때,
약수 : {1, 2, 3, 4, 6, 12} 이다.가장 큰 수를 찾는 것이니 12부터 arrayB의 원소를 나눈다 했을 때, 하나라도 나눠지게 된다면.. 당연히 12의 약수들로도 해당 원소를 나눌 수 있게 되므로 공약수까지 계산하는 의미가 없어진다.
즉 arrayA 원소의 최대공약수로 arrayB를 나누어보고, 나누어진다면 바로 arrayB의 원소의 최대공약수로 arrayA를 나누어보면 된다. 둘다 만족하지 않는다면 기본값인
answer = 0이 되는 것이고.
