2024.04.26 - Restore IP Addresses

[wlsgh7608]

문제 - 링크

문제 풀이

• 주어진 문자열을 이용하여 가능한 ip주소를 가진 리스트 반환하기

주어진 문자열을 자르면서 ip주소를 완성할 것임

• ip는 4개의 정수와 . 으로 이루어짐
• 주어진 문자열을 1~3개씩 잘라서 4개의 정수로 이루어지는 지 확인!

ip 주소 자르기

• 문자열에서 앞에서부터 1,2,3개씩 잘라서 유효한 ip주소인지 확인(255이하, 0xx로 시작하지 않는 ip)

적합한 ip인지 확인

    boolean isValidIp(String s, int len) {
        // len의 길이로 자를 수 없는 경우
        if (s.length() < len) {
            return false;
        }
        String currentString = s.substring(0, len);
        // 0으로 시작하는 경우
        if (currentString.length() > 1 && currentString.charAt(0) == '0') {
            return false;
        }
        int currentInt = Integer.parseInt(currentString);
        // 255보다 큰 경우
        if (currentInt > 255) {
            return false;
        }

        return true;
    }

코드

class Solution {
    List<String> list = new ArrayList<>();


    boolean isValidIp(String s, int len) {
        // len의 길이로 자를 수 없는 경우
        if (s.length() < len) {
            return false;
        }
        String currentString = s.substring(0, len);
        // 0으로 시작하는 경우
        if (currentString.length() > 1 && currentString.charAt(0) == '0') {
            return false;
        }
        int currentInt = Integer.parseInt(currentString);
        // 255보다 큰 경우
        if (currentInt > 255) {
            return false;
        }

        return true;
    }

    // xxx.xxx.xxx.xxx 형태로 변환
    String getIpAddress(String[] ip) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 4; i++) {
            sb.append(ip[i]);
            if (i != 3) {
                sb.append(".");
            }
        }
        return sb.toString();
    }

    void dfs(int depth, String s, String[] ip) {
        if (depth == 4) {
            // 아직 남아있는 문자열이 있다면 완성하지 못한 것임
            if (!s.isEmpty()) {
                return;
            }
            String ipAddress = getIpAddress(ip);
            list.add(ipAddress);
            return;
        }
        // 앞에서부터 1~3개 짤라봄
        for (int i = 1; i <= 3; i++) {
            if (!isValidIp(s, i)) {
                continue;
            }
            ip[depth] = s.substring(0, i);
            String remainString = s.substring(i);
            dfs(depth + 1, remainString, ip);
        }
    }

    public List<String> restoreIpAddresses(String s) {
        String[] ip = new String[4];
        dfs(0, s, ip);
        return list;
    }

}

실행 시간