[Java] LeetCode 93. Restore IP Addresses

[Java] LeetCode 93. Restore IP Addresses

 

문   제 : 

숫자로만 이루어진 String s가 주어진다.

s에 적절히 점을 4개 추가하여 만들수 있는 유효한 IP주소 String을 모두 찾아서 List<String> 형태로 반환해라.

 

{ 1 <= s.length <= 20 }

{ s consists of digit only. }

 

 

A valid IP address consists of exactly four integers separated by single dots.
Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, 
"0.1.2.201" and "192.168.1.1" are valid IP addresses,
but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, 
return all possible valid IP addresses that can be formed by inserting dots into s. 
You are not allowed to reorder or remove any digits in s.
You may return the valid IP addresses in any order.

 

Example )

Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

///////////////////////////////////////////////////////

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

 

---

접   근 : 

점을 찍을 수 있는 자리를 하나씩 찾고, 점을 찍으며 유효한 IP주소를 모두 찾는다.

재귀함수로 구현한다.

재귀함수로 불러질 때마다 점 개수를 늘려가고, 가능한 상황에서만 문자열을 추가해 나간다.

 

유효한 IP조소가 되기 위한 조건 : 

점이 4개여야 한다.

각 자리의 숫자는 0~255 사이 숫자여야 한다. (포함)

점과 점 사이는 숫자로만 이루어져 있어야 한다.

011, 032와 같이 다른 숫자 앞에 0이 올 순 없다.

 

 

---

해   결 : 

결과 값을 담을 List<String> 을 선언한다.

재귀함수를 작성한다.

 

재귀함수 내용 : 

점이 4개 이상이면 안된다. (예외처리)

 

점이 4개가 됐고, 문자열을 끝까지 검사하여 추가했다면 결과 List에 저장해준다.

 

0~255숫자가 3자리 수 이므로 숫자의 길이를 1칸에서 3칸까지 검사해준다.

여기서, 1~3 칸을 검사할 때 전체 문자열의 길이를 넘어서면 안된다. (검사하는 마지노선을 정해주어야함)

또, 한 자리 숫자가 아닌데 첫 자리가 0인 경우가 있으면 안 된다. ex) 011, 032

1~3칸을 숫자로 변환하고, 0~255사이의 숫자라면 통과이다. 다음 자리 숫자를 검사해야 한다. (재귀함수)

여기서 저장되어 이어지고 있는 문자열은 추가하고 있던 string + "." 이고, 점의 개수와 index를 각각 증가시켜 부른다.

 

 

---

결과 값을 담을 List<String> 을 선언한다.

 

 

List<String> res = new ArrayList<>();

 

 

---

 

재귀함수를 호출한다.

solve(res, s, "", 0, 0);

 

---

 

solve 함수를 작성한다.

 

public void solve(List<String> res, String s, String temp, int index, int dots) {
    if (dots > 4) return;

    if (dots == 4 && index >= s.length()) {
        res.add(temp.substring(0,temp.length()-1));
        return;
    }

    for (int i=1; i<=3 && index+i <= s.length(); i++) {
        String num = s.substring(index, index + i);

        if (num.charAt(0) == '0' && i != 1) break;

        else if (Integer.parseInt(num) <= 255) {
            solve(res, s, temp + s.substring(index, index+i) + ".", index+i, dots+1);
        }
    }
}

res : 유효한 IP주소를 모두 저장한 결과 List

s : 입력 받은 String

temp : 지금 내가 유효한 IP주소를 만들기 위해 가공하고 있는 String

index : 내가 검사하고 있는 s 문자열의 자리

dots : 내가 이때까지 추가한 점의 개수

 

res에 추가할 땐 temp의 맨 끝에 붙어있는 "."을 하나 떼고 저장해야 하기 때문에 temp.substring을 활용하였다.

 

 

---

결   과  :

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();

        solve(res, s, "", 0, 0);
        
        return res;
    } 

    public void solve(List<String> res, String s, String temp, int index, int dots) {
        if (dots > 4) return;

        if (dots == 4 && index >= s.length()) {
            res.add(temp.substring(0,temp.length()-1));
            return;
        }

        for (int i=1; i<=3 && index+i <= s.length(); i++) {
            String num = s.substring(index, index + i);

            if (num.charAt(0) == '0' && i != 1) break;

            else if (Integer.parseInt(num) <= 255) {
                solve(res, s, temp + s.substring(index, index+i) + ".", index+i, dots+1);
            }
        }
    }
}