[프로그래머스] 소인수분해 unique, erase

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

프로그래머스

정수 n의 소인수를 담은 배열을 반환하는 메서드를 만든다.

for문으로 순차적으로 n을 분해해가며 소인수를 answer 벡터에 넣는다.

이때 answer에는 중복된 소인수가 들어가 있을 수 있으므로 마지막에 unique로 중복을 제거한다.

unique만 실행하게 되면 unique 값에 남은 answer 값이 함께 있으므로 erase로 지워준다.

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

using namespace std;

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

unique

algorithm 헤더 안의 함수이다.

내부 기능은 아래와 같이 동작한다.

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return last;

  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
}

위 문제를 예를 들어서 내부 기능을 설명하자면,

 

first 는 answer.begin(), last는 answer.end()로

만약 10000이 n으로 들어왔을 때, 배열에 들어오게 되는 소인수는 2,2,2,2,5,5,5,5이다.

answer.begin()은 가장 앞의 2를 가리키고, answer.end()는 가장 뒤에 5를 가리킨다.

 

이때, unique에 들어가게 되면

index 0번의 2에서 index 7의 5까지 중복을 검사한다.

 

first 를 돌리면서 *result와 같지 않은 값이 있으면 result에 넣는다.

먼저 result = first 에서 index 0번의 2가 result에 들어간다.

이후 index 3번의 2와 index 4번의 5가 같지 않은데 이때 result의 다음 인덱스에 5를 넣는다.

  

이후 result를 반환하는데, 이때 result는 2, 5 뒤에 초기 first값이 들어가 2,5,2,2,5,5,5,5 가 된다.

https://cplusplus.com/reference/algorithm/unique/

https://cplusplus.com/reference/algorithm/unique/

vector.erase

iterator erase (iterator position);iterator erase (iterator first, iterator last);

position에 있는 단일 element를 지우거나 first 에서 last까지의 elements를 지우는 함수이다.

지운 element 개수만큼 size도 줄여준다.

https://cplusplus.com/reference/vector/vector/erase/

https://cplusplus.com/reference/vector/vector/erase/