6. 숫자만 추출

it 취업을 위한 알고리즘 문제 풀이

문제

코드

//6.숫자만 추출
#include <stdio.h>

int main() {
    //freopen("input.txt", "rt", stdin);
    char str[51];
    scanf("%s", str);
    int res = 0;
    int cnt = 0;
    for (int i = 0; str[i]; ++i) {
        if (str[i] >= 48 && str[i] <= 57) {
            res = res * 10 + (str[i] - 48);
        }
    }

    for (int i = 1; i * i <= res; ++i) {
        if (i * i == res) {
            ++cnt;
            break;
        }
        if (res % i == 0) {
            cnt += 2;
        }
    }


    printf("%d\n%d", res, cnt);
    return 0;
}

문제해결방법

• 배열명은 주소값을 나타내므로 포인터와 같고 %s 서식 지정자를 통해 문자열을 str에 저장된 주소, 즉, str을 시작으로 하는 배열에 저장한다. 이때 C언어 문자열 저장 규칙에 따라 마지막 문자열 뒤에는 NULL값이 저장된다.
• 이렇게 문자를 입력 받은후 아스키 코드에서 '0'문자 '9'문자에 해당하는 48과 57사이에 있으면 0~9 숫자문자를 나타내고 해당 문자라면 10진수 정수로 저장하면 된다.
  • 10진수 정수로 저장하는 방법은 가장 최근에 저장된 수에 10배를 해서 위치 기수법에서 왼쪽으로 한칸 옮기고 최근에 입력된 숫자를 오른쪽 위치에 저장하면 된다.
  • 숫자를 저장할 변수에 초기값으로 0으로 설정하면 위에 코드는 최초 추출 되는 숫자 문자를 처음 일의 자리 숫자로 문제 없이 저장할 수 있다.
  • 주의 할점은 문자를 숫자로 만들기 위해서는 해당 문자의 아스키코드에서 -48을 해주면 된다. 이유는 '0'문자는 아스키코드에서 48로 저장되어 있고 실제 0으로 만들기 위해서는 -48을 해주어 실제 0으로 저장시켜야한다. '1'문자도 마찬가지이다. '1'문자는 아스키코드로 49로 현재 49로 저장되어 있으므로 1로 만들어 저장하기 위해서는 -48을 해주어야 한다.
• 이제 위에서 추출한 숫자의 약수를 구하는 방법에서는 1부터 해당 숫자를 나누면서 나누어 떨어지면 카운트 값을 1씩 증가시키면 되는데 여기서 조금더 효율적인 계산을 위해서 약수의 규칙을 이용해 코드를 조금 변형했다.
• i값을 1부터 1씩 증가시키면서 문자열에서 추출한 숫자(res)를 i값으로 나누어서 나누어 떨어지는 경우를 찾으면 된다. 이때 약수는 항상 짝을 가지게 되므로 i는 i*i가 res보다 작거나 같은 시점까지만 계산을 해주면 된다. 그리고 나누어 떨어지는 숫자가 존재하면 +2씩 증가시켜 주면 되는데, 이때 예외 사항은 짝이 자기자신인 숫자이다. 즉, i값의 제곱이 해당 숫자(res)가 될때 이다. 이때는 약수의 개수를 1증가 시켜야 한다. 그리고 i는 바로 이시점까지만 반복문을 수행하고 다음부터는 더이상 약수를 구하지 않아도 된다. 이유는 이미 짝지어진 개수를 구했기 때문이다.
  • 예를 들면 64의 경우 1,2,4,8,16,32,64의 약수를 갖는데 1은 64와 짝을 이루고 2는 32와 짝을 이루고 4는 16과 짝을 이루게 된다. 그리고 for문의 조건에서 i가 8일 때 8*8<=64에서 등호 조건까지 성립하고 i가 9일 때부터는 성립되지 않으므로 반복문이 종료된다.
  • 다른 예시로 12의 경우는 1,2,3,4,6,12의 약수를 갖고 제곱하여 추출한 숫자(res)가 되는 약수를 갖지 않는 경우이다. 여기서 for문의 조건을 보면 i는 1부터 3까지 증가할때 매번 조건을 만족한다. 3의 경우에도 3*3<=12에서 for문의 부등호 '<' 조건을 만족하고 제곱하여 12가 되지 않으므로 짝을 이루는 약수 4까지 카운트 값으로 계산하여 +2를 누적한다. 그리고 다음 i가 4일때 반복문 조건이 4*4 <=12 조건이 만족하지 않아 종료된다.