[Inflearn] Ugly Number(three point) (interview source)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 소인수분해 했을 때 그 소인수가 2 or 3 or 5 로만 이루어진 수가 Ugly Number, 못생긴(?) 숫자라고 한다..

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 먼저 2, 3, 5 의 배수를 체크해준 후, N번째로 체크된 수를 찾으면 될 것 같다.

     

     Ugly Number 를 보면 

     1 2 3 4 5 6 8 9 10 12 15 ... 이다.

     여기서 반대로 Ugly Number 가 아닌 숫자를 찾아보자.

     7 11 13 14 17

     7 이상의 소수이면서, 소수의 배수는 Ugly Number 가 아니다. 

     N 까지 7 이상의 소수이면서 소수의 배수를 1로 체크한 후 

     마지막에 원소의 값이 0인 index들 중 N 번째 수를 출력하면 되겠다!

    2 3 5의 배수를 체크한다기엔 소수가 소인수에 포함되는 경우(ex. 14)가 있고,

    계속 2 3 5 로 나누어떨어지는지 체크한다해도 언제까지 체크해주고 어느 타이밍에 count 를 해주어야할지

    알 수 없는 노릇이다. N 이 1500 일 때, 결과가 859963392 인 것을 보면, N 이 커졌을 때 결국 시간초과로 해결해내지 못 하게 된다.

  2. 시간 안에 해결할 수 있는 방법이 떠오르지 않아 결국 강사님의 힌트를 얻었다.  

     기존에 배웠던 two point 가 아닌 three point 를 사용한 문제였다..!

     차근차근 과정을 밟아보자.

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1
	p2
	p3
	p5

먼저 1을 초기값으로 설정한다. 3개의 포인터도

 

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2
	p2 = 2
	p3 = 3
	p5 = 5

그 다음 각 포인터에 자신의 배수에 맞는 수를 곱해준다. 2 or 3 or 5

여기서 최솟값을 구한다. = 2

최솟값을 다음 index에 넣어주고 사용한 포인터를 ++ 해준다.

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3
		p2 = 4
	p3 = 3
	p5 = 5

다음도 마찬가지로 각 포인터에 자신의 배수에 맞는 수를 곱해준다.

최솟값 = 3

최솟값을 다음 index에 넣어주고 사용한 포인터를 ++

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4
		p2 = 4
		p3 = 6
	p5 = 5

계속 동일한 방법으로 수행한다.

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5
			p2 = 6
		p3 = 6
	p5 = 5

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6
			p2 = 6
		p3 = 6
		p5 = 10

여기서 다음 최솟값을 구하려고 했는데 동일한 숫자가 나왔다.

이럴 경우 마찬가지로 최솟값을 다음 index에 넣어준 후 사용한 두 포인터를 모두 ++ 해주면 된다.

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6	8
				p2 = 8
			p3 = 9
		p5  = 10

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6	8	9
					p2 = 10
			p3 = 9
		p5  = 10

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6	8	9	10
					p2 = 10
				p3 = 12
		p5  = 10

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6	8	9	10	12
						p2 = 12
				p3 = 12
			p5 = 15

 

index	1	2	3	4	5	6	7	8	9	10
Ugly Num	1	2	3	4	5	6	8	9	10
							p2 = 16
					p3 = 15
			p5 = 15

 

이 과정을 코드로 옮겨보자!

 

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int Ugly[1501];
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int n, i, p2 = 1, p3 = 1, p5 = 1, min, tmp2, tmp3, tmp5;
 
    scanf("%d", &n);
 
    Ugly[1] = 1;
 
    for (i = 2; i <= n; i++)
    {
        tmp2 = Ugly[p2] * 2;
        tmp3 = Ugly[p3] * 3;
        tmp5 = Ugly[p5] * 5;
 
        if (tmp2 < tmp3)
        {
            if (tmp2 < tmp5)
                min = tmp2;
            else
                min = tmp5;
        }
        else
        {
            if (tmp3 < tmp5)
                min = tmp3;
            else
                min = tmp5;
        }
 
        Ugly[i] = min;
        
        if (tmp2 == min) p2++;
        if (tmp3 == min) p3++;
        if (tmp5 == min) p5++;
    }
 
    printf("%d\n", Ugly[n]);
 
    return 0;
}

풀긴 했다만.. 영 찝찝한 이 기분은 뭘까ㅠㅠ

스스로 해결해내지 못 한 이 찝찝함...

나중에 다시 꼭 풀어봐야지..

#. Other code

#include <bits/stdc++.h>
 
using namespace std;
 
int a[1501];
 
int main(){
    int n, i, p2, p3, p5, min=0;
 
    scanf("%d", &n);
    a[1]=1;
    p2=p3=p5=1;
 
    for(i=2; i<=n; i++){
        if(a[p2]*2<a[p3]*3) min=a[p2]*2;
        else min=a[p3]*3;
        if(a[p5]*5<min) min=a[p5]*5;
        if(min==a[p2]*2) p2++;
        if(min==a[p3]*3) p3++;
        if(min==a[p5]*5) p5++;
        a[i]=min;
    }
 
    printf("%d\n", a[n]);    
    return 0;
}

역시.. Soooo 깰끔 하시다

line 12 에서 변수 선언 시 '1'로 초기화하는 방법도 있지만 이렇게 하는 방법도 좋은 것 같다.

line 15~17 을 보면 나 같은 경우 엄청 복잡하고 헷갈리게 세 수의 최솟값을 구했는데

강사님은 단 3줄만에 세 수의 최솟값을 구하셨다..

세 수를 비교할 때, 두 수를 먼저 비교한 후 그 결과에 마지막 수를 비교하니 더 간편하게 구할 수 있다는 것을 알게 되었다.

세 수의 최댓값을 구할 때도 이와 같은 방식으로 구현하면 좋을 것 같다.

#. Result

  - Input --------------------------------------------------------

10

------------------------------------------------------------------

  - Output --------------------------------------------------------

12

------------------------------------------------------------------