[Java] 백준 26902번 - IP-adresser

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

 

▼ 문제 번역 ▼

문제
IPv4 주소는 마침표로 구분된 0에서 255 사이의 정수 4개(각각 앞에 0이 있어서는 안 됨)로 구성됩니다. 예를 들어. 1.0.3.255는 유효한 주소이고, 1.0.03.255, 1.0.3.256 및 1.0.3은 유효한 주소가 아닙니다. 일련의 숫자가 주어지면 해당 숫자에 마침표 3개를 삽입하여 생성할 수 있는 유효한 IPv4 주소를 모두 찾으세요.

입력
첫 번째 줄에는 최소 4자리, 최대 12자리의 ​​문자열이 포함됩니다.

출력
정수를 인쇄하세요: 점 3개를 삽입하여 형성할 수 있는 유효한 IP 주소의 수입니다.

===================================================================

 

0~255 숫자가 4개로 이루어진 IPv4 주소를 만들 수 있는 경우의 수를 구하는 문제이다.

 

숫자가 그렇듯이 0이 될 수는 있지만 0으로 시작하는 04, 004, 044 등이 불가능함에 유의해야한다. (String을 잘라야 하기 때문에 저런 숫자들이 만들어 질 수 있음)

 

입력은 일련 4~12자리의 숫자가 들어오며, 여기에 마침표 3개를 삽입해야 한다.

1~3자리의 숫자들이 있으면 될 것이고, dfs를 이용하여 자리수의 배열을 구해주었다.

 

예를 들어 291841 라는 입력이 들어올 경우, 6자리 이므로

1, 1, 2, 2

1, 1, 3, 1

1, 2, 1, 2

1, 2, 2, 1

2, 1, 1, 2

2, 1, 2, 1

2, 2, 1 ,1 자리로 배분할 수 있을것이다.

 

이를 입력에 맞게 배분해보면 아래와 같은 IP주소들이 만들어진다.

1. 2.9.18.41
2. 2.9.184.1
3. 2.91.8.41
4. 2.91.84.1
5. 29.1.8.41
6. 29.1.84.1
7. 29.18.4.1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static String address;
    static int count;

    static void input(String[] lines) {
        address = lines[0];
        count = 0;
    }

    static String process() {
        dfs(new int[4], 0);
        return String.valueOf(count);
    }

    static void dfs(int[] list, int depth) {
        if (depth == 4) {
            int sum = 0;
            for (int i : list) {
                sum += i;
            }
            if (sum == address.length() && isValid(list)) {
                count++;
            }
            return;
        }

        for (int i = 1; i <= 3; i++) {
            list[depth] = i;
            dfs(list, depth + 1);
        }
    }

    private static boolean isValid(int[] list) {
        int idx = 0;
        for (int i : list) {
            String s = address.substring(idx, idx + i);
            if (s.length() == 2 && s.startsWith("0") ||
                s.length() == 3 && s.startsWith("00")) return false;
            int intS = Integer.parseInt(s);
            if (intS > 255) {
                return false;
            }
            idx += i;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        input(readLines());
        System.out.println(process());
    }

    private static String[] readLines() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> lines = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null && !line.isEmpty()) {
            lines.add(line);
        }
        br.close();

        String[] linesArray = new String[lines.size()];
        linesArray = lines.toArray(linesArray);
        return linesArray;
    }
}