코딩테스트 -- 숫자 카드 나누기 - (프로그래머스 / 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 해 주세요.

 

---

간단하게 영희의 카드들을 모두  나눌수있는 숫자는 철수의 카드들을 모두 나누지는 못하는 정수, 그리고 그 반대의 정수 중에 가장 큰값을 골라내는 쉬운 문제!

 

숫자는 크지만

"나눌수 있다!" >> 라는 부분에서 조금 줄여 갈수있을것 같습니다.

 

저는 2 ~ 영희의 최솟값 으로 한번 나눠보고

2 ~ 철수의 최솟값 으로 나눠 보는것 까지만 확인하여 풀었습니다.

 

 

 

 

바로 시작!

---

가장 먼저 나누어 지는지 부터 확인해 주는 함수를 만들어 주고

void find(int max,vector<int>&array,int a){
    
    bool check=0;
    
    for(int i=2;i<=max;i++){
        check=1;
        for(int j : array){
            if(j%i!=0 and check){
                check=0;
                break;
            }
        }
        if(check){
            if(a){
                A_list.push_back(i);
            }
            else{
                B_list.push_back(i);
            }  
        }
    }
}

 

다음은 상대에게 안 나눠지는 수를 찾아주며 최댓값을 구해주었습니다.

void max_find(vector<int>list,vector<int>&array){
    
    bool check=0;
    
    for(int i : list){
        check=1;
        for(int j : array){
             if(j%i==0 and check){
                check=0;
                break;
            }
        }
        
         if(check){
            max_answer=max(max_answer,i);
        }
    }
    
}

 

위의 함수를 차례대로 사용해주면 

 

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    sort(arrayA.begin(),arrayA.end());
    sort(arrayB.begin(),arrayB.end());
    
    find(arrayA[0],arrayA,1);
    find(arrayB[0],arrayB,0);
    
    max_find(A_list,arrayB);
    max_find(B_list,arrayA);
    
    
    return max_answer;
}

먼가 깔끔한 솔루션이 완성되네요!

 

 

 

 

ALL

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


using namespace std;

    
int max_answer=0;
vector<int>A_list;
vector<int>B_list;


void find(int max,vector<int>&array,int a){
    
    bool check=0;
    
    for(int i=2;i<=max;i++){
        check=1;
        for(int j : array){
            if(j%i!=0 and check){
                check=0;
                break;
            }
        }
        if(check){
            if(a){
                A_list.push_back(i);
            }
            else{
                B_list.push_back(i);
            }  
        }
    }
}


void max_find(vector<int>list,vector<int>&array){
    
    bool check=0;
    
    for(int i : list){
        check=1;
        for(int j : array){
             if(j%i==0 and check){
                check=0;
                break;
            }
        }
        
         if(check){
            max_answer=max(max_answer,i);
        }
    }
    
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    sort(arrayA.begin(),arrayA.end());
    sort(arrayB.begin(),arrayB.end());
    
    find(arrayA[0],arrayA,1);
    find(arrayB[0],arrayB,0);
    
    max_find(A_list,arrayB);
    max_find(B_list,arrayA);
    
    
    return max_answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!