[BAEKJOON] NO.1977 완전제곱수

오늘은 1977번 완전제곱수를 풀었다

다 풀고나서 보니 3달 전에 이미 풀었었음,,ㅎ
근데 이 때랑 풀이는 조금 다른 것 같다

완전제곱수는 정수의 곱으로 나타낼 수 있는 수를 말한다.
ex. 정수가 n이면 n x n으로 만들어질 수 있는 수 (64, 81, 100, ..)

1. 3달 전 풀이 (C)

#include <stdio.h>

int main(void)
{
    int m = 0, n = 0;
    scanf("%d", &m);
    scanf("%d", &n);

    int i, j;
    int isPresence = 0;
    int arr[n-m];

    int idx = 0;
    int sum = 0;
    for(i=m; i<=n; i++)
    {
        // 완전 제곱 수 찾기
        for(j=1; (j*j)<=i; j++)
        {
            if(j*j==i)
            {
                arr[idx++] = i;
                isPresence = 1;
            }
        }
    }

    int min = arr[0];
    for(i=0; i<idx; i++)
    {
        sum += arr[i];
        if(arr[i] < min)
        {
            min = arr[i];
        }
    }

    if(isPresence)
        printf("%d\n%d\n", sum, min);
    else
        printf("-1\n");
    
    return 0;
}

2. 오늘 푼 것 (C++)

#include <iostream>
using namespace std;

int main(void)
{
    int m = 0, n = 0;

    cin>>m;
    cin>>n;

    int size = 100;
    int perfect_square_numbers[100];

    int startIdx = 0; // 탐색 시작 인덱스 구하기
    bool isGetStartIdx = false;
    for(int i=1; i<= size; i++)
    {
        perfect_square_numbers[i-1] = (i*i);
        // 만약 완전제곱수의 값이 m보다 크면 그 전 수가 startIdx가 됨 
        if(!isGetStartIdx)
        {
            if (perfect_square_numbers[i - 1] > m)
            {
                startIdx = i - 2;
                isGetStartIdx = true;
            }
        }
        
    }

    int total = 0;
    bool isFindMin = false;
    int min = 0;
    for(int i=m; i<=n; i++)
    {
        for(int j=startIdx; j<size; j++)
        {
            if(i == perfect_square_numbers[j])
            {
                if(!isFindMin)
                {
                    min = i;
                    isFindMin = true;
                }
                total += i;
            }
        }

    }

    if(total == 0 && min == 0)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<total<<endl;
        cout<<min<<endl;
    }
    
    return 0;
}

3. 오늘 푼 것의 개선 버전?

• 처음에 배열을 100번 인덱스까지 전부 채우는 것이 비효율적인 것 같아서
  endIdx도 정해주었다.
• 그리고 변수를 너무 많이 써서 윗 쪽에 정리해주었다.

#include <iostream>
using namespace std;

int main(void)
{
    int m = 0, n = 0;
    int min = 0;
    int total = 0;
    int size = 100;
    int startIdx = 0; // 탐색 시작 인덱스 구하기
    int endIdx = 0;
    
    bool isGetStartIdx = false;
    bool isGetEndIdx = false;
    bool isFindMin = false;
    bool isFindPerfect = false;

    int perfect_square_numbers[100];

    cin>>m;
    cin>>n;

    for(int i=1; i<= size; i++)
    {
        perfect_square_numbers[i-1] = (i*i);
        // 만약 완전제곱수의 값이 m보다 크면 그 전 수가 startIdx가 됨 
        if(!isGetStartIdx)
        {
            if (perfect_square_numbers[i - 1] > m)
            {
                startIdx = i-2;
                isGetStartIdx = true;
            }
        }
        else if(!isGetEndIdx)
        {
            if(perfect_square_numbers[i-1] >= n)
            {
                endIdx = i-1;            
                isGetEndIdx = true;
                break;
            }
        }
    }
    
    // 완전제곱수 찾기
    for(int i=m; i<=n; i++)
    {
        for(int j=startIdx; j<=endIdx; j++)
        {
            if(i == perfect_square_numbers[j])
            {
                isFindPerfect = true;
                if(!isFindMin)
                {
                    min = i;
                    isFindMin = true;
                }
                total += i;
            }
        }
    }

    if(!isFindPerfect)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<total<<endl;
        cout<<min<<endl;
    }
    
    return 0;
}

3달 전에 푼 게 더 간단하고 효율적인 것 같아서 뭐지? 싶다 ㅠ
Unity 하다 와서 그런가 Unity 식으로 푼 것 같기도 하고 ㅋㅋㅋㅋㅋ
뭔가 이 문제는 뿌듯함보다 아쉬움이 크다

배열을 쓴 이유는 입력 값의 최대가 10000이어서
그럼 size가 100인 배열만 만들면 된다고 생각했고 나름 간단하게 보였다.

미리 완전제곱수 배열을 만들어두면
그 다음은 범위의 값과 배열의 값을 비교해서 total과 min을 구하면 되니까
m에서 n까지 돌면서 계산을 하는 것보다 계산량이나 시간이 단축될 것이라 생각했다.

이후 개선버전으로 나마
나름대로 start Idx나 end Idx를 제한시켜줘서 더 계산량을 줄이기는 했다..
다음에는 배열을 안쓰려고 노력해봐야겠다