프로그래머스[programmers] - 숫자 카드 나누기(C++)[LV2]

📕문제

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

프로그래머스

---

🔎문제 풀이

양수 a가 될 수 있는 조건은 2가지 있습니다.

1. 철수가 가진 카드들을 전부 나눌 수 있고, 영희가 가진 모든 카드를 나눌 수 없어야 합니다.
2. 영희가 가진 카드들을 전부 나눌 수 있고, 철수가 가진 모든 카드를 나눌 수 없어야 합니다.

 

그렇다면 a의 후보는 철수가 가진 약수이거나, 영희가 가진 약수여야 합니다.

이때 각 약수들은 상대방들의 약수가 되어서는 안 됩니다.

 

 

풀이 방식은 다음과 같습니다.

1. 철수가 가진 카드와, 영희가 가진 카드를 오름차순으로 정렬해 줍니다.
   (문제에서 오름차순으로 주어진다는 얘기가 없어서, 오름차순으로 정렬해 줍니다)
2. 철수의 첫 번째 카드에서 약수, 영희의 첫번째 카드에서 약수를 각각 구해줍니다.
   • 오름차순으로 정렬한 이유는 만약 5,10,20이라면 10의 약수인 10은 5를 나눌 수 없기 때문에,
     가장 작은 카드의 약수를 구해주는 것입니다. 
     
     • 즉 뒤의 원소들의 약수를 구해봤자, 첫 번째 원소를 나눌 수 없기 때문입니다.
3. 그렇다면 각각의 약수들을 자신의 카드들과 비교해서 나눌 수 있는지 체크하고,
   나눌 수없다면 지워줍니다.
4. 철수의 약수들을 영희의 전체 카드와 계산하고, 영희의 약수들을 철수의 전체 카드와 계산해 줍니다.
5. 남은 약수들 중 가장 큰 숫자가 답이 될 것입니다.

약수를 구하는 방식은 1부터 시작해서 숫자의 절반까지 검사해서 나눠 떨어진다면 약수로 판별하고 map에 넣어줬습니다.

저는 숫자의 절반까지 검사를 했는데, 만약 숫자의 끝까지 검사를 한다면 시간초과가 날 수 도 있기 때문에 주의하시면 될 거 같습니다.

 

자료구조는 map을 사용했습니다.

철수의 map과 영희의 map을 사용해서, 각각의 원소들을 추가해 주고, 지우는 작업을 했습니다.

(다 풀고 생각해 보니 굳이 map을 안 써도 될 거 같긴 한데.. 처음 풀이에서는 map을 사용해서 다양한 작업을 할 거 같아서 map을 선택했습니다.)

💻코드

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <map>
using namespace std;
// 1.철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수a
// 2.영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌수 없는 양의 정수 a
//즉 자신이 가진 수를 나눌 수 있고, 상대방이 가진 수를 나눌 수 없는 수가 a가 될것이다.
map<int,int>A_map;
map<int,int>B_map;
map<int,int> funct(vector<int>ary){
    int num = ary[0];
    map<int,int>m;
    for(int i=1; i<=sqrt(num);i++){ //절반까지 약수를 구한다.
        if(num%i==0){ //i가 약수라면
            if(m.find(i)==m.end()){ //map에 처음 들어갓다면.
                m.insert(make_pair(i,0));
                m.insert(make_pair(num/i,0));
            }
        }
    }
    for(auto iter = m.begin(); iter!=m.end();iter++){ //그 다음 자기가 속한 원소들을 나눌 수 있는 지 체크하고, 나눌 수 없다면 지워줌.
        for(int j=1; j<ary.size();j++){
            if(ary[j]%iter->first!=0){
                m.erase(iter->first);
                break;
            }
        }
    }
    return m;
}
map<int,int> find_map(map<int,int>m, vector<int>ary){ //m에 있는 원소들을 상대편 배열과 비교하기
     for(auto iter = m.begin(); iter!=m.end();iter++){
        for(int i=0; i<ary.size();i++){
            if(ary[i]%iter->first==0){ //나누어 떨어지면 안됨.
                m.erase(iter->first); //map에서 지운다.
                break; //중단.
            }
        }
    }
    return m;
}
int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    //오름차순으로 정렬하기
    sort(A.begin(),A.end());
    sort(B.end(),B.end());
    
    A_map=funct(A);
    B_map=funct(B);
    if(A_map.size()!=0)
        A_map=find_map(A_map,B);
    if(B_map.size()!=0)
        B_map=find_map(B_map,A);    
    for(auto iter=A_map.begin(); iter!=A_map.end();iter++){
        answer=max(answer,iter->first);
    }
    for(auto iter=B_map.begin();iter!=B_map.end();iter++){
        answer=max(answer,iter->first);
    }    
    return answer;
}