Today I Learned

오늘은 Leetcode 자바 코테 공부!

Validate IP Address

Leetcode 468번 https://leetcode.com/problems/validate-ip-address/description/

문제

Given a string queryIP, return "IPv4" if IP is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.

A valid IPv4 address is an IP in the form "x1.x2.x3.x4" where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, "192.168.1.1" and "192.168.1.0" are valid IPv4 addresses while "192.168.01.1", "192.168.1.00", and "192.168@1.1" are invalid IPv4 addresses.

A valid IPv6 address is an IP in the form "x1:x2:x3:x4:x5:x6:x7:x8" where:
1 <= xi.length <= 4
xi is a hexadecimal string which may contain digits, lowercase English letter ('a' to 'f') and upper-case English letters ('A' to 'F').
Leading zeros are allowed in xi.

• 입력
  Input: queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
• 출력
  Output: "IPv6"

문제 풀이

• 이 문제는 알고리즘 위주의 코테보단 노가다에 가까운 String을 다루는 문제이지만 IP 주소를 다루고 있어서 한번 풀어보았다. 처음엔 정규식으로 풀어보려 했지만 오히려 정규식이 처리 속도가 더 느리다는 포스트를 본 적이 있어서 메서드별로 나눠서 조건판별로 풀이했다. 정규식 관련한건 추후 포스트에 한번 정리해보려 한다.

1. validIPAddress() 메서드는 가장 바깥 메서드로 아래의 private 메서드를 이용해 v4인지 v6인지 판별한다.

2. isValidIPv4() 메서드에서는 문자열의 길이, 마침표로 시작하거나 끝나는지 판단하고, ip를 .을 기준으로 분리한다. 토큰의 수가 4개가 아니면 틀리고, 토큰이 유효한지 isValidIPv4Token() 메서드로 넘긴다. 토큰 유효성은 여러개를 보기 위해 try-catch문으로 잡아서 토큰이 0~255 사이인지 판단한다.

3. isValidIPv6() 메서드는 문자열 길이, 콜론으로 시작하는지 판단하고, ip를 :을 기준으로 분리한다. 토큰의 수가 8개가 아니면 틀리고, 토큰이 유효한지 isValidIPv6Token() 메서드로 넘긴다. 토큰 유효성은 여러개를 보기위해 for문으로 char를 하나하나씩 보면서 이 문자가 아스키 코드로 숫자인지, 대문자인지, 소문자인지 판단해 셋다 아니면 false로 반환하게한다.

4. 위의 메서드를 거쳐 IPv4, IPv6, Neither를 판단하고 반환하면 완료!

Java 코드

public class Solution {
    public String validIPAddress(String IP) {
        if(isValidIPv4(IP))
            return "IPv4";
        else if(isValidIPv6(IP))
            return "IPv6";
        else
            return "Neither";
    }
    
    private boolean isValidIPv4(String ip) {
        if(ip.length()<7) return false;
        if(ip.charAt(0)=='.') return false;
        if(ip.charAt(ip.length()-1)=='.') return false;
        String[] tokens = ip.split("\\.");
        if(tokens.length!=4) return false;
        for(String token:tokens) {
            if(!isValidIPv4Token(token)) return false;
        }
        return true;
    }
    
    private boolean isValidIPv4Token(String token) {
        if(token.startsWith("0") && token.length()>1) return false;
        try {
            int parsedInt = Integer.parseInt(token);
            if(parsedInt<0 || parsedInt>255) return false;
            if(parsedInt==0 && token.charAt(0)!='0') return false;
        } catch(NumberFormatException nfe) {
            return false;
        }
        return true;
    }
    
    private boolean isValidIPv6(String ip) {
        if(ip.length()<15) return false;
        if(ip.charAt(0)==':') return false;
        if(ip.charAt(ip.length()-1)==':') return false;
        String[] tokens = ip.split(":");
        if(tokens.length!=8) return false;
        for(String token: tokens) {
            if(!isValidIPv6Token(token)) return false;
        }
        return true;
    }
    
    private boolean isValidIPv6Token(String token) {
        if(token.length()>4 || token.isEmpty()) return false;
        char[] chars = token.toCharArray();
        for(char c:chars) {
            boolean isDigit = c>=48 && c<=57;
            boolean isUppercaseAF = c>=65 && c<=70;
            boolean isLowerCaseAF = c>=97 && c<=102;
            if(!(isDigit || isUppercaseAF || isLowerCaseAF))
                return false;
        }
        return true;
    }
}