99클럽 코테 스터디 2일차 TIL : x만큼 간격이 있는 n개의 숫자,

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

프로그래머스

뭐지??? 문제가 너무 쉬웠다...

그래서 또 시간초과 나려는건가,, 했는데 그것도 아니고,, 뭐지?????????????

---

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(int x, int n) {
    vector<long long> answer;
    
    for(int i = 0; i<n; i++){
        answer.push_back(x + x*i);
    }
    
    return answer;
}

설명하고 말것도 없다 이게뭐임??????

 

---

그래서 챌린저 문제도 풀어보려고 한다!

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

프로그래머스

문제 자체는 간단했다!

냅다 최대공약수 구해서 다른 배열에 전부 나눠보면 되었다.

 

31번 테스트케이스를 계속 통과하지 못해서 끙끙댔는데......

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

using namespace std;

// a > b
int gcd(int a, int b){
    int mod = a%b;
    if(mod == 0){
        return b;
    }
    return gcd(b, mod);
}

int gcds(vector<int> a){
    //sort(a.begin(), a.end()); // 오름차순
    int gcdd = a[0];
    for(int i = 1; i<a.size(); i++){
        if(gcdd > a[i]){
            gcdd = gcd(gcdd, a[i]);
        }else{
            gcdd = gcd(a[i], gcdd);
        }
    }
    return gcdd;
}

bool is_devided(vector<int> vec, int n){
    // vec속 숫자들이 n으로 나눠지는지 (하나라도 나눠지는게 있으면 true)
    for(int i = 0; i < vec.size(); i++){
        if((vec[i] % n) == 0){
            return true;
        }
    }
    return false;
}


int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    // 조건 1 확인
    int culgcd = gcds(arrayA);
    if(!is_devided(arrayB, culgcd)){
        answer = culgcd;
    }
    
    // 조건 2 확인
    int yunggcd = gcds(arrayB);
    if(!is_devided(arrayA, yunggcd)){
        if(answer < yunggcd){
            answer = yunggcd;
        }
    }
    
    
    return answer;
}

gcds함수에서 배열을 정렬하지 않고 풀었어야 했다.

gcd함수가 무조건 a > b를 만족하도록 원소를 넣어줘야해서 그렇게 했는데,

그냥 반복돌릴때 비교해서 gcd함수를 실행하도록 변경해주었더니 해결되었다!

 

처음에는 최대공약수를 구하고 -> 모든 공약수를 찾아서 전부 is_devide로 확인해주었다.

근데 다른 배열을 절내 '나누지' 못하는 최대값 a를 찾는 문제이므로, 최대공약수보다 더 작은 숫자는 고려할 필요가 없어다.

최대공약수로 나누어지는게 없으면, 더 작은 숫자들을 확인할 필요가 없고,

최대공약수로 나누어지는 숫자가 있으면, 더 작은 숫자들로도 당연히 나누어지기 때문이다.

 

모든 공약수로 확인을 한다고 해도 시간초과가 나지는 않는것같지만 (그렇게 풀었을때에도 31번테케빼고 전부 통과했음)

더 같단하게 풀리는 방법이 있다!

 

아무튼,,, 챌린저도 생각보다 쉽게 풀려서 당황했다ㅎ..