[알고리즘] Ugly Number

문제 내용

• 어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number라고 부릅니다. Ugly Number를 차례대로 적어보면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …….입니다. 숫자 1은 Ugly Number의 첫 번째 수로 합니다. 자연수 N이 주어지면 Ugly Number를 차례로 적을 때 N번째 Ugly Number를 구하는 프로그램을 작성하세요.

입력설명

• 첫 줄에 자연수 N(3<=N<=1500)이 주어집니다.

10

출력설명

• 첫 줄에 N번째 Ugly Number를 출력하세요.

12

구현 방식

• 다중 포인터 알고리즘
• 곱하기 2 를 해주는 포인터, 곱하기 3을 하는 포인터, 곱하기 5를 하는 포인터를 생성하고, 포인터 자리수을 1로 한다.
• 현재 포인터 자리수에 위치한 값에서 포인터 값만큼 곱했을 때 최소가 되는 포인터 값을 채택하고 포인터 자리수를 1 추가한다.
• 이때 최소가 되는 포인터가 여러개면, 똑같이 1추가 시켜준다.
• 나는 포인터가 p2 p3 p5 이런식으로 쓰면 코드가 더러울것같아서, 벡터로 만든다음에 for 문을 돌렸는데, 더 더러워진 느낌.

// Pointer 구조체 생성 후 벡터로 사용

struct Pointer
{
    Pointer() {}
    Pointer(int idx, int value) { this->idx = idx; this->value = value; }
public:
    int idx = 0;
    int value = 0;
};

void solution(int N) {
    vector<int> uglyNumbers = vector<int>(N+1, 0);
    uglyNumbers[1] = 1;
    vector<Pointer> pointers = vector<Pointer>{ Pointer(1,2), Pointer(1,3), Pointer(1,5) };
    
    for (int i = 2; i <= N; i++)
    {
        pair<vector<int>, int> minValue = make_pair(vector<int>(), INT_MAX);
        for (int j = 0; j < pointers.size(); j++)
        {
            int candidateValue = uglyNumbers[pointers[j].idx] * pointers[j].value;
            if (minValue.second < candidateValue)
                continue;
            if (minValue.second > candidateValue)
            {
                minValue.first.clear();
                minValue.first.resize(0);
                minValue.second = candidateValue;
            }
            minValue.first.push_back(j);

        }
        uglyNumbers[i] = minValue.second;
        for(auto it = minValue.first.begin(); it != minValue.first.end() ; it++)
            pointers[*it].idx++;
    }
    cout << uglyNumbers[N];
}

// 정렬하여 최소값 구한 후 같은 수 포인터 값 증가
void solution(int N) {
    vector<int> uglyNumbers = vector<int>(N+1, 0);
    uglyNumbers[1] = 1;
    int p2, p3, p5;
    p2 = p3 = p5 = 1;
    for (int i = 2; i <= N; i++)
    {
        vector<int> candidataValues = vector<int>{ uglyNumbers[p2] * 2 ,uglyNumbers[p3] * 3, uglyNumbers[p5] * 5 };
        sort(candidataValues.begin(), candidataValues.end());
        if (candidataValues[0] == uglyNumbers[p2] * 2) p2++;
        if (candidataValues[0] == uglyNumbers[p3] * 3) p3++;
        if (candidataValues[0] == uglyNumbers[p5] * 5) p5++;
        uglyNumbers[i] = candidataValues[0];
    }

    cout << uglyNumbers[N];
}