c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q39 아름다운 IP 주소

[문제]

IP 주소는 XXX.XXX.XXX.XXX 형식으로 이루어져 있다. 예를 들어, 123.45.234.9 이런 식이다.

(최대 255.255.255.255까지 가능하다)

이 IP 주소를 2진법으로 표현하기로 한다.

123.45.234.9 => 01111011.00101101.11101010.00001001

이 때, 2진법으로 표현된 IP 주소가 대칭수인 가짓수는?

단, 원래의 IP 주소는 0 ~ 9까지 총 10개의 숫자가 1번씩 모두 사용된다고 한다.

예를 들어, 198.76.54.230는 0 ~ 9 숫자가 모두 사용된 IP 주소이다. (54를 054 이렇게 표시하지는 않는다고 한다.)

 

 

[알고리즘]

1) 0 ~ 9까지 숫자가 1번씩만 사용되어야 하므로 다음과 같은 숫자들은 모두 제거된다.

22, 77, 114, 220 등등

2) 위에서 제거되지 않은 숫자들에 대해서 2진수끼리 서로 대칭인 숫자를 구한다.

예를 들어, 1의 대칭수는 128이고, 2의 대칭수는 64, 3의 대칭수는 192이다.

3) 대칭수 역시 22, 77, 114, 220 등 같은 숫자가 2번 이상 나타난다면 제외한다. 또한, 원래 수와 대칭 수가 같은 숫자를 공유하면 제외한다. 예를 들어, 1의 대칭수는 128인데 1을 공유하므로 제외한다.

1) ~ 3) 조건을 모두 만족하는 경우는 아래와 같다.

4) IP[4] 배열을 만들고 숫자를 대입한다. => A.B.C.D

이 중 A와 D는 서로 대칭수이고, B와 C는 서로 대칭수이다.

따라서, 앞의 A, B 2개 숫자만 채우면 C, D는 자동으로 결정된다.

A, B, C, D가 모두 결정되면 이들 숫자들이 같은 숫자를 공유하는지 확인한다.

만약 같은 숫자를 공유하면 제외한다.

 

5) 만약 A.B.C.D가 정답이면 D.B.C.A도 정답이고, B.D.A.C도 정답이다. 1가지 케이스에 대해서 가능한 조합의 개수는 8개이다.

따라서, 다음과 같은 조건을 추가한다.

A < B, A < D, B < C

 

6) 0 ~ 9까지 숫자가 모두 사용되었는지 확인한다.

만약, 0 ~ 9까지 숫자가 1번씩 모두 사용되면, 숫자 10개에 . 이 3개 있으므로 문자열의 길이는 13이어야 한다.

문자열이 13인 것만 출력한다.

아래는 전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <string.h>
#define SZ 256
#define DIGIT 8
int get_mirror(int num);
bool check_num(int* check, int num);
void convert(int* arr, int num, int base);
int inverse_convert(int* arr, int sz, int base);
void reverse_arr(int* arr, int sz);
void initiate(int* arr, int sz);
void copy_arr(int* arr1, int* arr2, int sz);
void print_arr(int* arr, int sz);
int main() {
    int IP[4] = { 0 };
    int check[10] = { 0 };
    int copy[10] = { 0 };

    for (int i = 0; i < SZ; i++) {
        initiate(check, 10);
        if (check_num(check, i) == false)
            continue;
        int mirror_num = get_mirror(i);
        if (i >= mirror_num)
            continue;
        if (check_num(check, mirror_num) == false)
            continue;
        IP[0] = i, IP[3] = mirror_num;
        copy_arr(copy, check, 10);
        for (int j = i + 1; j < SZ; j++) {
            copy_arr(check, copy, 10);
            if (check_num(check, j) == false)
                continue;
            mirror_num = get_mirror(j);
            if (j >= mirror_num)
                continue;
            if (check_num(check, mirror_num) == false)
                continue;
            IP[1] = j, IP[2] = mirror_num;
            char ip[20];
            sprintf(ip, "%d.%d.%d.%d", IP[0], IP[1], IP[2], IP[3]);
            if (strlen(ip) == 13)
                printf("%s\n", ip);
        }
    }
}
bool check_num(int* check, int num) {
    int copy[10] = { 0 };
    copy_arr(copy, check, 10);
    while (num != 0) {
        if (copy[num % 10] != 0)
            return false;
        copy[num % 10]++;
        num /= 10;
    }
    copy_arr(check, copy, 10);
    return true;
}
int get_mirror(int num) {
    int arr[DIGIT] = { 0 };
    convert(arr, num, 2);			// 2진법으로 변환 후 arr 배열에 저장
    reverse_arr(arr, DIGIT);		// 배열의 순서를 뒤바꿈
    return inverse_convert(arr, DIGIT, 2);	// 다시 숫자로 변환하여 반환
}
void convert(int* arr, int num, int base) {
    for (int i = DIGIT - 1; i >= 0; i--) {
        arr[DIGIT - i - 1] = num / (int)pow(base, i);
        num %= (int)pow(base, i);
    }
}
int inverse_convert(int* arr, int sz, int base) {
    int num = 0;
    for (int i = 0; i < sz; i++)
        num += arr[i] * (int)pow(base, DIGIT - i - 1);
    return num;
}
void reverse_arr(int* arr, int sz) {
    for (int i = 0; i < sz / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[sz - 1 - i];
        arr[sz - 1 - i] = temp;
    }
}
void copy_arr(int* arr1, int* arr2, int sz) {
    for (int i = 0; i < sz; i++)
        arr1[i] = arr2[i];
}
void initiate(int* arr, int sz) {
    for (int i = 0; i < sz; i++)
        arr[i] = 0;
}
void print_arr(int* arr, int sz) {
    for (int i = 0; i < sz; i++)
        printf("%d", arr[i]);
    printf("\n");
}

 

아래는 정답. 1가지 케이스가 존재하며, 8가지 조합이 가능하다.

34.179.205.68 // 68.179.205.34 // 34.205.179.68 // 68.205.179.34

179.34.68.205 // 179.68.34.205 // 205.34.68.179 // 205.68.34.179