99클럽 코테 스터디 2일차 TIL, 프로그래머스 / 숫자카드 나누기

 

 

1번째 풀이

#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

bool divideAllA(int curMid, const vector<int>& arrayA)
{
    for (const int aNum : arrayA) if (aNum % curMid != 0) return false;
    return true;
}

bool divideNoneA(int curMid, const vector<int>& arrayA)
{
    for (const int aNum : arrayA) if (aNum % curMid == 0) return false;
    return true;
}

bool divideAllB(int curMid, const vector<int>& arrayB)
{
    for (const int bum : arrayB) if (bum % curMid != 0) return false;
    return true;
}

bool divideNoneB(int curMid, const vector<int>& arrayB)
{
    for (const int bum : arrayB) if (bum % curMid == 0) return false;
    return true;
}

void getDivideNums(int num, set<int>& divideN)
{
	for (int i = 1; i <= sqrt(num); i++)
    {
        if (num % i == 0)
		{
			divideN.insert(i);
			if (i != num / i) divideN.insert(num / i);
		}
    }
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    set<int> divideNSet;
    
    // 일단 vec 형태로 모아두고
    // 오름차순 정렬
    // 뒤에서부터 set 에 넣기
    // set 앞에서부터, 순회하면서, 조건 검사
    // 만약 만족하는 대상이 존재하면 break, answer 에 세팅
    
    for (int num : arrayA) getDivideNums(num, divideNSet);
    for (int num : arrayB) getDivideNums(num, divideNSet);
    
    // for (int idx = divideNVec.size() - 1; idx >= 0; --idx)
    for (auto it = divideNSet.rbegin(); it != divideNSet.rend(); ++it) 
    {
        // int num = divideNVec[idx];
        int num = *it;
        
        // std::cout << "num : " << num << std::endl;
        
        if (divideAllA(num, arrayA) && divideNoneB(num, arrayB))
        {
            answer = num;
            break;
        }
        if (divideNoneA(num, arrayA) && divideAllB(num, arrayB))
        {
            answer = num;
            break;
        }
    }
    
    return answer; 
}

 

즉, 모든 가능한 약수 들을 set 에 모아두고, set 은 오름차순 정렬이므로

뒤에서부터 차례대로 조건에 맞는 숫자인지를 검사하는 로직을 짰다.

하지만, 일부 문제들에서 시간초과가 났다.

 

2번째 풀이

#include <string>
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

// 최대 공약수를 구해주는 함수
int lcm(int a, int b)
{
    int t;
    
    while(b != 0)
    {
        t = a % b;
        a = b;
        b = t;
    }
    
    return a;
}

int checkNotDivided(vector<int>& array, int div)
{
    for (int num : array) 
        if (num % div == 0) 
            return 0;
    return div;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    
    // 방향
    // 1) 각 array 의 최대공약수를 구한다 (조건을 만족하는 최대 크기의 숫자를 구하는 것)
    // 2) arrayA 의 최대공약수로 arrayB 를 나눠보고, 그 반대도 수행
    // 조건 만족하는 최대 숫자를 리턴
    int answer = 0;
    
    int lcm_a = arrayA[0];
    int lcm_b = arrayB[0];
    
    // 기존 최대공약수와, 현재 array 원소 간의 최대 공약수를 구해가는 것일까 ?
    // - 기존 최대공약수가 나눠질 수 있다면, 지금까지 조사한 원소들도 나눠질 수 있는 숫자라는 것.
    // - 어떻게 보면, 점차 범위를 좁혀가되, 지속해서 큰 값을 유지하고 싶은 것이다.
    for (int n : arrayA) lcm_a = lcm(lcm_a, n);
    for (int n : arrayB) lcm_b = lcm(lcm_b, n);
    
    answer = checkNotDivided(arrayA, lcm_b);
    answer = max(checkNotDivided(arrayB, lcm_a), answer);
    
    return answer; 
}

 

최대 공약수 개념을 사용하여 새로운 코드를 짰다.