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번테케빼고 전부 통과했음)
더 같단하게 풀리는 방법이 있다!
아무튼,,, 챌린저도 생각보다 쉽게 풀려서 당황했다ㅎ..
'코테준비 > 하루한개도전~' 카테고리의 다른 글
99클럽 코테 스터디 3일차 TIL : 문자열 내 마음대로 정렬하기 (1) | 2024.07.24 |
---|---|
7/23 TIL : 완전탐색 (2) | 2024.07.24 |
7/22 TIL : 완전탐색 (5) | 2024.07.23 |
99클럽 코테 스터디 1일차 TIL : n^2배열 자르기 (2) | 2024.07.22 |
[코드트리 조별과제] : 1주차 (0) | 2024.07.21 |