[알고리즘] 8번째 알고리즘 문제

[SongGwanSeok]

📝 Description

무엇을?

• https://leetcode.com/problems/ugly-number-ii/description/
• https://leetcode.com/problems/ugly-number-iii/description/

왜?

• (ex 사용자를 인증하기 위해)

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[SongGwanSeok]

https://leetcode.com/problems/ugly-number-ii/description/ 시간 초과

class Solution {
public:
    int nthUglyNumber(int n) {
        int cur = 1;
        int nonUglyNum = 1;

        while(cur < n){
            nonUglyNum++;
            int curNum = nonUglyNum;

            while(curNum % 2 == 0){
                curNum /= 2;
            }
            while(curNum % 3 == 0){
                curNum /= 3;
            }
            while(curNum % 5 == 0){
                curNum /= 5;
            }

            if(curNum == 1){
                cur++;
            }
        }

        return nonUglyNum;
    }
};

[SongGwanSeok]

성공 but, 찝찝함 1 <= n <= 1690 이 조건이면 int로 반환이 안되는데 왜 문제는 int를 반환하라고 했을까

class Solution {
public:
    long long nthUglyNumber(int n) {
        priority_queue<long long, vector<long long>, greater<long long>> uglyNumTable;
        uglyNumTable.push(1);

        for(int i = 0; i < n-1; i++){
            long long curNum = uglyNumTable.top();
            while(uglyNumTable.size() > 0 && curNum == uglyNumTable.top()){
                uglyNumTable.pop();
            }
            uglyNumTable.push(curNum * 2);
            uglyNumTable.push(curNum * 3);
            uglyNumTable.push(curNum * 5);
        }

        return uglyNumTable.top();
    }
};

[SongGwanSeok]

코드 개선 - vector에 저장한 값을 바로 return 하니 int가 넘는 수도 넘어가네 이유가 뭘까

int nthUglyNumber(int n) {
    int a = 0, b = 0, c = 0;
    vector<int> uglyTable(n+1);
    uglyTable[0] = 1;

    for(int i = 0; i < n; i++){
        int curNum = min(min(uglyTable[a] * 2, uglyTable[b] * 3), uglyTable[c] * 5);
        uglyTable[i+1] = curNum;

        if(curNum == uglyTable[a] * 2){
            a++;
        }
        if(curNum == uglyTable[b] * 3){
            b++;
        }
        if(curNum == uglyTable[c] * 5){
            c++;
        }
    }

    return uglyTable[n-1];
}