[프로그래머스] Level 2. 숫자 카드 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

 

해결 방법

1. 두 배열을 정렬한다. 배열 A 속 숫자가 모두 나누어진다면, 배열 A속 최소숫자보다 작거나 같다는 의미이다.
2. candidates에 후보숫자들을 넣는다. 후보의 범위는 배열 A중 최솟값과 배열 B중 최솟값중 큰 수이다. 
3. A로 나누어 떨어져야하는지, B로 나누어떨어져야하는지 정보를 함께 저장해주기 위해 map을 사용한다.
4. 이제 배열을 돌면서, candidates 가 여전히 정답일 수 있는지 하나씩 검사한다. 그리고 아니라면 즉시 candidates에서 제거해버린다. 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;

    //두 배열을 정렬. 답은 가장 작은 수보다 작거나 같다.
    sort(arrayA.begin(), arrayA.end());
    sort(arrayB.begin(), arrayB.end());
    
    map<int,bool> candidates; //숫자, A로 나누어떨어지는쪽인지
    
    
    int m = max(arrayA[0], arrayB[0]);
    for(int i=2; i<= m; i++){
        bool isA = i <=arrayA[0] && arrayA[0]%i == 0;
        bool isB = i <=arrayB[0] && arrayB[0]%i == 0;
        if(isA == isB) continue;
        candidates.insert({i,isA});
    }
    
    for(int i=0; i<arrayA.size(); i++){
        for(auto it = candidates.begin(); it != candidates.end() ;){
           int num = it->first; bool isA = it->second;
            
            
            if ((isA && arrayA[i] %num != 0) || (isA &&arrayB[i] %num== 0) 
               || (!isA && arrayA[i]%num == 0) || (!isA && arrayB[i]%num !=0)) {
                it = candidates.erase(it); // erase 후 반환된 유효한 반복자로 갱신
            } else {
                ++it; // 삭제하지 않을 경우 다음 요소로 이동
            }
        }
    }
    
    if(candidates.size() ==0) return 0;
    
    for(auto it = candidates.begin(); it !=candidates.end(); it++){
        if(answer < (*it).first)  answer = (*it).first;    
    }
    return answer;
}