[프로그래머스] 숫자 카드 나누기 Swift

숫자 카드 나누기

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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. 나누어지지 않는 숫자중 최댓값 출력

4. 없다면 0

 

-> 시간초과

주어진 원소의 최댓값이 1억이라서 이방법으로 한다면 최대공약수를 구하는 반복문만 최대 1억번 돌리게된다..

 

두번째 접근법: 유클리드 호제법

시간을 단축하기위해 단순반복방법이 아닌 유클리드호제법으로 최대공약수를 구하는 시간을 줄인다.

1. 배열마다 유클리드호제법으로 최대공약수를 구한다. 반복은 배열의 갯수만큼(최대 50만번)

2. 구한 최대공약수로 상대배열을 나눠본다.

3. 나눠지면 0으로 초기화, 안나누어지면 그대로

4. 두개의 최대공약수중 최댓값 출력(둘다 나누어졌다면 0이되고, 한쪽만 나누어진다면 그 값이 최대가됨)

 

-> 성공

 

코드로 구현하면 다음과 같다.

import Foundation

// 유클리드를 이용한 gcd 재귀호출
func gcd(_ num1: Int,_ num2: Int) -> Int {
    if num2 == 0 {
        return num1
    } else {
        return gcd(num2, num1 % num2)
    }
}
func solution(_ arrayA:[Int], _ arrayB:[Int]) -> Int {
    var fA = arrayA[0]
    var fB = arrayB[0]
    
    //A의 최대공약수
    for i in arrayA {
        fA = gcd(fA,i)
    }
    //B의 최대공약수
    for i in arrayB {
        fB = gcd(fB,i)
    }
    // A의 최대공약수로 B를 나눠봄, 나눠지면 0
    for i in arrayB {
        if i % fA == 0 {
            fA = 0
            break
        }
    }
    // B의 최대공약수로 A를 나눠봄, 나눠지면 0
    for i in arrayA {
        if i % fB == 0 {
            fB = 0
            break
        }
    }

    return max(fA, fB)
}