개발 블로그

문제 링크 : https://www.acmicpc.net/problem/2064

문제

네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워크 주소’와 ‘네트워크 마스크’라는 두 개의 정보로 표현된다.

IP 주소는 네 개의 바이트로 구성되어 있으며, 각각을 10진수로 나타내고(앞에 0을 붙이지 않은 형태로) 사이에 점을 찍어 주소를 표현한다. 바이트이기 때문에 각각의 수는 0부터 255까지의 값을 갖게 된다. 네트워크 주소와 네트워크 마스크 역시 같은 형식으로 나타낸다.

IP 네트워크에 대해 올바르게 이해하기 위해서는 위와 같은 주소를 2진수로 이해하면 된다. 즉, 각각의 바이트를 8자리의 이진수로 나타내고, 이를 네 개 붙여놓은(앞에서부터) 32자리의 이진수를 생각해 보자. IP 네트워크에는 기본적으로 2m 개의 컴퓨터(혹은 IP 주소)가 할당될 수 있다. 이 경우의 네트워크 주소는 앞의 32-m 자리가 임의의 수(0 또는 1)로 구성되어 있고, 뒤의 m자리는 0으로 채워지게 된다. 네트워크 마스크는 앞의 32-m 자리가 1로 채워져 있고, 뒤의 m자리는 0으로 채워지게 된다. 이와 같은 IP 네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP들이 포함되게 된다.

예를 들어 네트워크 주소가 194.85.160.176이고, 네트워크 마스크가 255.255.255.248인 경우를 생각해 보자. 이 경우, 이 네트워크에는 194.85.160.176부터 194.85.160.183까지의 8개의 IP 주소가 포함된다.

어떤 네트워크에 속해있는 IP 주소들이 주어졌을 때, 네트워크 주소와 네트워크 마스크를 구해내는 프로그램을 작성하시오. 답이 여러 개인 경우에는 가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

입력

첫째 줄에 정수 n(1≤n≤1,000)이 주어진다. 다음 n개의 줄에는 각 컴퓨터의 IP 주소가 주어진다.

출력

첫째 줄에 네트워크 주소를, 둘째 줄에 네트워크 마스크를 출력한다.

접근 방법

1) 입력받은 각 ip 주소를 의미하는 문자열을 '.'를 기준으로 split 하여 inputIp[]에 넣는다. 다음 바이트 자리 숫자를 입력받을때는, 먼저 왼쪽으로 8비트를 shift한 뒤에 입력받은 숫자를 or 연산을 이용하여 inputIp[]를 갱신한다.

2) 주소의 4byte 즉 32bit에서 하나라도 다른 비트가 나온 첫 비트를 찾는다. 

   i                            31 ...     24 23... 16  15...      8   7...         0

  194.85.160.177 = 10000010 1010101 10100000 10110001

  194.85.160.183 = 10000010 1010101 10100000 10110111

  194.85.160.178 = 10000010 1010101 10100000 10110010

에서는, 첫번째부터 i = 31이라고 했을 때 i=31...3까지는 모두 비트가 일치하다가 i=2에서 일치하지 않는 비트가 처음으로 생긴다.

비트가 일치했던 i=31...3에 대해서는 subnet |= 1 연산을 통해서 

subnet : 11111111 11111111 11111111 11111000 (255.255.255.248) 를 만들어 놓는다.

4) print() 에 파라미터로 subnet & inputIp[0]를 넘겨서 네트워크 주소를 출력하고, 

subnet도 넘겨서 네트워크 마스크를 출력한다.

print() 가 동작하는 원리

for문에서 shift의 값은 24, 16, 8,0 순으로 변한다. 

그래서 32비트로 넘어온 num을 네파트로 나눠서 1byte씩 8비트의 수를 십진수로 출력하게 되는 것이다. 

(1<<8) -1 는 2^8에서 1을 뺀 수로 8비트가 1로 이루어진 수를 의미한다. 이 수와 & 연산을 한다는 것은 num>>shift의 값 중 8비트만 출력하겠다는 의미이다. 

//
//  SM_BOJ2064_IP주소.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//3:42
//

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

void print(int num){    //num은 32비트 수 -> 8비트씩 끊어서 십진수로 출력해야함
    
    int shift = 24;
    for(int i = 0; i<4; i++, shift -= 8){
        cout << ((num>>shift) & (1<<8)-1);  //31bit->7bit... 24bit->0bit /// 23bit->7bit...
        if(i != 3) cout << '.';
    }
    cout << "\n";
}
int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    int n; cin >> n;
    string ip;
    
    //ip 주소 입력
    int inputIp[n];
    for(int i = 0; i<n; i++){
        cin >> ip;
        istringstream ss(ip);
        string tmp;
        while(getline(ss,tmp,'.')){
            inputIp[i] <<= 8;       //8비트 왼쪽으로 shift 해서 자리 만들고
            inputIp[i] |= stoi(tmp);    //or 연산
        }
    }
    
    int subnet = 0; //inputIp[n]들이 모두 어디 byte까지 같은지
    //각 바이트 자리끼리 비교해서 달라지는 비트 몇번 비트인지 확인
    int netAddr = 0;
    for(int i = 31; i>=0; i--){
        
        int bit = 1 << i;   //i만큼 왼쪽 shift -> &연산을 통해 오른쪽에서 i번째 비트를 뽑아 비교하기 위함.
        bool isContinue = true;
        for(int r=1; r<n; r++){
            if((inputIp[0] & bit) != (inputIp[r] & bit)){//기준은 첫번째로 입력한 ip 주소.
                isContinue = false;         //비트 달라지는 즉시 검사 중단.
                break;
            }
        }
        if(!isContinue) break;
        else {
            subnet |= bit;         //n개의 ip주소에 대해 해당 비트가 모두 같으면 1로 채워나감.
            
        }
    }
    
    //subnet : 11111111 11111111 11111111 11111000 (255.255.255.248)
    
    print(subnet & inputIp[0]); //뒤에 m개만(다른부분만) 0으로 만들고 앞의 32-m개는 inputIp[0]와 같게
    print(subnet);
    
    
    
    
    
    return 0;
}

참고 : (https://donggod.tistory.com/88)