[Programmers Level2] 숫자 카드 나누기(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

프로그래머스

[문제 설명]

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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에는 중복된 원소가 있을 수 있습니다.

[입출력 예]

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 합니다.

[문제 풀이]

문제에서 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구해야한다.

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

위 조건을 보고 떠오른 생각은 최대 공약수이다.
먼저 철수가 가진 카드들의 최대 공약수를 구하고 영희가 가진 카드들의 최대 공약수를 구한다.

(최대 공약수를 구하는 방법은 유클리드 호제법을 사용하였고 아래 포스트에 자세히 설명되어있다.)

[Algorithm] 유클리드 호제법 : 최대 공약수와 최소 공배수(C++)

구한 철수, 영희의 최대 공약수 중 큰 값을 answer 변수에 저장한다.
1) answer 변수에 저장한 값이 철수의 최대 공약수라면 영희가 가진 카드들로 해당 값이 나누어지는지 확인한다.
1-1) 나누어진다면 조건을 만족하지 않으므로 0을 리턴한다.
1-2) 나누어지지 않는다면 answer 변수를 리턴한다.

2) answer 변수에 저장한 값이 영희의 최대 공약수라면 철수가 가진 카드들로 해당 값이 나누어지는지 확인한다.
2-1) 나누어진다면 조건을 만족하지 않으므로 0을 리턴한다.
2-2) 나누어지지 않는다면 answer 변수를 리턴한다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int getGCD(vector<int>& arr) {
    int num1 = arr[0];
    for(int i = 1; i < arr.size(); ++i) {
        int num2 = arr[i];
        while(true) {
            int num3 = num2 % num1;
            if(num3 == 0) {
                break;
            }
            num2 = num1;
            num1 = num3;
        }
    }
    return num1;
}


int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    sort(arrayA.begin(), arrayA.end());
    sort(arrayB.begin(), arrayB.end());
    int gAnum = getGCD(arrayA); 
    int gBnum = getGCD(arrayB);

    answer = max(gAnum, gBnum);
    if(answer == gAnum) {
        for(int element : arrayB) {
            if(element % answer == 0) return 0;
        }
    } else {
        for(int element : arrayA) {
            if(element % answer == 0) return 0;
        }
    }

    return answer;
}