LeetCode : 264. Ugly Number II

[메인 로직]

idx1, idx2, idx3으로 2, 3, 5각각의 인덱스를 설정해주었다.

1을 먼저 배열에 넣어준 뒤, 1*2, 1*3, 1*5 각각의 값중 가장 작은 값을 그 다음 값으로 넣어준다.

그 후, 배열의 맨 뒤의 값과 2, 3, 5각각을 곱한 값이 같다면 해당 인덱스를 한 칸씩 이동해주었다.

아무래도 코드를 참고하는게 더 이해가 빠를 것 같다.

 

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n==1){
            return 1;
        }
        
        int ans = 0;
        int idx1 = 0, idx2 = 0, idx3 = 0;
        vector<int> v;
        v.push_back(1);
        n--;
        
        while(n--){
            int num = min(v[idx1]*2, min(v[idx2]*3, v[idx3]*5));
            ans = num;
            v.push_back(num);
            if(v.back()==v[idx1]*2) idx1++;
            if(v.back()==v[idx2]*3) idx2++;
            if(v.back()==v[idx3]*5) idx3++;
        }
        
        return ans;
    }
};