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

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

4673번: 셀프 넘버

1. 코드

#include <stdio.h>

int main(void)
{
    int i = 0, j, sum;
    int arr[10000] = {0, };
    
    for(i = 1; i <= 10000; i++)
    {
        sum = j = i;
        if(j >= 10000) { sum += j/10000; j %= 10000; }
        if(j >= 1000) { sum += j/1000; j %= 1000; }
        if(j >=100) { sum += j/100; j %= 100; }
        if(j >= 10) { sum += j/10; j %= 10; }
        
        sum += j;
        if(sum <= 10000) arr[sum] = 1;
        if(!arr[i]) printf("%d\n", i);
    }
    return 0;
}

 

2. 문제 해결 방식

예전에는 한 자리 수, 두자리 수, 세 자리 수 각각 나눠서 계산식을 만들고 해당하는 수가 셀프 넘버인지 아닌지 확인한 다음에 셀프 넘버를 출력했다면 이번에는 각각 나눈 과정을 없애고 한번에 처리하도록 만들어 보았다.

i의 수를 1부터 점점 증가시켜서 sum과 j에 i의 값을 저장한 뒤 j의 값과 i의 값은 같기 때문에 j의 값을 이용하여 각 자리의 값을 분리시켜서 sum에 더하고 그 값을 배열 arr의 sum만큼의 인덱스에 1을 저장한다. 1을 저장하는 이유는 sum값은 사실상 셀프 넘버가 아니기 때문에 셀프 넘버인지 아닌지 확인하기 위해 1을 저장한다.

그렇다면 배열에 1이 저장된 인덱스의 값은 셀프 넘버가 아니라는 것이다. 이때 sum값이 10000이하라는 조건을 붙였느데 붙인 이유는 배열의 길이는 10000인데 만약 이 길이를 넘는다면 오버플로우가 뜨기 때문에 그것을 방지하기 위해서 이다.

그리고 배열은 선언할 때 배열의 요소를 전부 0으로 초기화가 되어있기 때문에 요소가 0인 인덱스 값은 셀프 넘버이므로 해당하는 인덱스 값을 출력하면 된다.

4. 느낀점

예전에 풀었던 결과인데 총 크기는 1746b이고 걸린 시간은 220ms이다.

이 풀이는 총 크기는 470b이고 걸린 시간은 0ms이다.

크기 적으로는 4배 정도의 차이고 시간을 임의로 1ms라고 가정하고 계산하면 220배 차이다. 예전에 풀었지만 너무 문제를 풀기위해 풀었던 것 같다. 이제부터라도 천천히 효율적으로 속도를 증가시키고 크기를 줄이면서 알아보기 쉬운 코드를 만드는 작업에 집중해봐야겠다.