Lv 0. 소인수분해

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

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<int> tmp;
    for(int i=2; i<=n; i++){
        if(n%i==0){
            while(n%i==0){
                n/=i;
                tmp.emplace_back(i);
            }
        }
    }
    for(int i=0; i<tmp.size(); i++){
        if(i!=0 && tmp[i-1]==tmp[i]) continue;
        answer.emplace_back(tmp[i]);
    }
    return answer;
}

처음에는 이 문제를 가장 효율적으로 해결하기 위해서는 에라토스테네스의 체(https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)를 이용해서 10'000 개 까지의 소수들을 구한뒤에 각 소수들에 대해서 연산을 하는 형태의 코드를 작성하는것이 가장 좋겠다 싶었는데, 아무래도 n의 사이즈가 작아서 에라토스테네스의 체를 구현하는 코드를 작성하는 것보다는 그냥 조건에 맞는 연산을 하는 코드를 작성하는 방향으로 해결해보았다. 그와같은 방법으로 작성한 코드가 위에 첨부되어있는 형태의 코드이다. 

 

다른 사람의 풀이에서 위와 같은 형태의 로직으로 작성한 코드가 있는데 한번 첨부해보자면, 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    int num = 2;
    while(n!=1)
    {
        if(n % num == 0){
            n = n / num;
            answer.push_back(num);   
        }
        else
            num++;
    }
    sort(answer.begin(),answer.end());
    answer.erase(unique(answer.begin(),answer.end()),answer.end());
    return answer;
}

이런 형태로 작성한 코드가 있는데, 이렇게 작성하는것 또한 괜찮아보인다. 

결국 로직은 같은데 코드의 작성에서 깊이감이 3단까지 들어가는 형태가 아니다보니까, 좀 얕아보여서 더 눈에 잘 들어오는것 같다. 

중복된 요소가 있을텐데 그러한 요소에 대해서는 

answer.erase(unique(answer.begin(),answer.end()),answer.end()); 을 이용해서 제거해주었다. 

unique함수의 경우는 유니크 한것들을 앞으로, 중복된것들을 뒤로 쭉 변형시켜주고, 중복된 부붙이 나오는 곳의 이터레이터를 반환하는 함수로 기억하는데, 해당 함수를 사용한 방법을 보니까 그렇게 작동하는 함수가 맞는것으로 보여진다. 

나같은 경우에는 tmp 벡터를 새로 만들고, 해당 벡터에는 중복을 허용해서 받고, 그리고 나서 answer 벡터에 옮겨 담을때 중복된것은 제외하고 옮겨담는 방식으로 구현했다. 

어떤 방식을 사용하여도 상관은 없을거같은데, erase() unique() 를 활용한 형태의 중복제거는 다음에도 사용하게 될 일이 또 있을 것이다. 다음에 또 이와같은 형태의 코드가 나오면 다시 한번 짚고 넘어가고 더욱 내 눈에 익숙해지게 만들도록 하자. 

 

  Comments,     Trackbacks