백준 알고리즘 4673번: 셀프 넘버 C언어(개선)

문제 출처: www.acmicpc.net/problem/4673

4673번: 셀프 넘버

1. 코드

#include <stdio.h>

int sum(int n)          //셀프넘버가 아닌 수를 구하는 함수
{
    int sum = n;
    
    while(n>0)
    {
        sum += n%10;
        n/=10;
    }
    return sum;
}
int main(void)
{
    int arr[10001], i, check;
    
    for(i=1; i<10001; i++)
    {
        check = sum(i);
        if(check <10001)       //셀프 넘버가 아닌 수 확인
            arr[check]=1;
    }
    
    for(i=1; i<10001; i++)
    {
        if(arr[i]!=1)          //셀프 넘버 수 확인
            printf("%d\n", i);
    }
    return 0;
}

2. 느낀 점

우선 이 풀이 방식은 다른 코드를 찾아보다가 알게 된 방법이다. 이 방법은 배열의 인덱스 값을 이용하여 풀어낸 것인데 우선 10000이하의 숫자이니 10001크기의 배열을 만들고 셀프 넘버가 아닌 수, 즉 생성자가 없는 수를 구하여 그 숫자를 해당되는 배열의 인덱스와 일치시켜 배열에 특정한 key값을 할당시킨다면 이제 그 배열은 key값이 할당된 공간과 아무것도 없는 공간이 함께 할 것이다. 마무리로 그 특정 key값을 제외한 나머지 배열의 인덱스 값을 출력하면 그 값은 바로 우리가 원하던 생성자가 없는 수인 셀프 넘버일 것이다.

전에 풀어본 방법과 이 방법을 비교하자면 많이 차이가 난다.

먼저 개선한 방법의 풀이의 결과인데 시간을 보면 0ms정도 걸렸지만

개선하기 전에 풀어본 방법은 220ms나 걸렸다. 만약 개선한 방법의 시간을 1ms라고 해도 220배나 속도가 차이가 난다는 것이다.

이러한 방법을 찾아내고 이해하며 다시 한번 작성해보면서 이 문제를 풀면서 정말 아직도 내가 많이 부족하고 배울게 많다는 것을 느꼈다. 문제를 풀어도 그것에 안주한다면 그거야말로 발전이 없다는 것도 다시 한번 깨달았다. 앞으로는 성실하게 알고리즘에 대해 공부를 해야겠다.