Lv 0. 약수 구하기. *다시 풀어보기*

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

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    for(int i=1; i<=n; i++){
        if(n%i==0) answer.emplace_back(i);
    }
    return answer;
}

 

내가 작성한 코드의 경우는 위와 같은데 ,이것보다 더욱 줄일 수 있는 아주 단순한 방법을 다른 사람의 풀이에서 보니, 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    for(int i = 1; i<=n/2; i++)
    {
        if(n % i == 0)
            answer.push_back(i);
    }
    answer.push_back(n);
    return answer;
}

이렇게 i를 절반까지만 구하고, 맨 마지막에 자기 자신의 값에 해당하는 n의 값을 넣어주는 방식으로 구하면 훨씬 더 적은 경우의 수로 약수들을 계산할 수 있게 된다. 약수가 가장 작은 값은 결국 n/2 까지만 확인해도 되고, 그걸 넘어서는 값은 자기 자신에 해당하는 값이 된다는것을 이용하는 풀이이다. 이렇게 생각할줄 알아야 더욱 더 효율적으로 프로그램을 작성할 수 있을 것이다. 좋은 풀이이다. 

 

거기서 더 추가적으로 생각해서, 중복되는 연산을 더 줄일 수 있도록 하는 풀이를 첨부해보면, 

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

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    for(int i=1; i*i<=n; i++){
        if(n%i==0){
            answer.push_back(i);
            if(i*i!=n) answer.push_back(n/i);
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

이런식의 풀이를 하는 것을 보게 되었는데, 이것은 약수가 있다면, 해당 약수와 n/i 라는 값을 둘다 넣어주면서 각각 수를 다시 계산하지 않아도 되지 않게 하는 풀이인데, 이때에 이 풀이는 sort 함수를 사용해야 하는데 sort를 할때의 시간복잡도까지 고려해야 하는 풀이이지만, 이 경우는 n이 커진다면 충분히 괜찮은 시간복잡도를 보여주는 풀이가 될 수 있다고 생각된다. 

n이 얼마나 큰 사이즈로 가느냐에 따라서 알고리즘 문제 풀이에서 더 효율적인 방식을 고려하는 방법을 생각해볼 수 있을 것이다. 

 

굉장히 간단한 문제였지만 계획을 세울때부터 어떻게 세우느냐에 따라서 효율적인 프로그램을 작성할 수 있는 방법이 많다는것을 알 수 있었다. 

 

굉장히 단순한 문제이지만 다시 풀어보면서 프로그램 이전에 더욱 더 간결하고 쉬운 방법은 뭐가 있을지 생각해보는게 큰 도움이 될 것이다.