Leetcode 93. Restore IP Addresses - Python

Leetcode 93 문제 보기

 

문제 이해하기

일련의 숫자 s가 주어진다. (1 <= s.length <= 20)

이를 이용해 유효한 IP 주소를 만들어보자.

IP 주소는 "192.168.1.1"처럼 4개의 정수가 "."으로 구분되어지며, 각각의 숫자는 0부터 최대 255까지 가능하다.

그러나 "01.0.0.0"처럼 0으로 시작하는 숫자는 불가능하다.

 

주어진 s로 만들 수 있는 가능한 IP 주소를 모두 출력하라.

 

아이디어 구상

가능한 IP 주소를 모두 출력해야하므로, Brute Force하게 풀어야하는 문제다.

이 때 적절한 pruning을 통해 효율적인 풀이가 가능하도록 고민해보자.

 

가장 먼저 눈에 뜨인 것은 1 <= s.length <= 20 라는 constraint다.

"."으로 구분되는 각각의 정수는 최대 0부터 255까지이므로, IP 주소는 "0.0.0.0"부터 "255.255.255.255"까지 가능하다.

때문에 s.length가 4보다 작거나 12보다 큰 경우에는 애초에 유효한 IP 주소를 만들 수 없다.

 

하지만 만약 4 <= s.length <= 12 인 s에 대해서는 어떻게 대처해야할까?

Decision Tree를 그리며 생각해보자.

s = "25525511135"인 test case를 살펴보자.

By Mesotes

DFS를 이용해 각 Leaf node까지 탐색하면서, 만들어질 IP 주소가 유효한지 검사한다.

유효하지 않은 경우는 다음과 같다.

1. 만약 s에서 정수를 제외한 나머지 뒷부분이 지나치게 많은 숫자(eg. "."이 하나 사용됐을 때, 뒤에 남은 숫자는 9개 이하여야한다)로 이루어져 있다면 유효하지 않다.

2. 만약 정수가 0으로 시작하면서 2자리수 이상의 숫자라면 유효하지 않다.

3. 만약 정수가 255보다 크다면 유효하지 않다.

 

Leaf node에 도달할때까지 유효성 검사를 통과했다면 res에 담고 다음 검사를 진행한다.

 

풀이

결과를 담을 리스트 res와 탐색 시 만들어지는 IP 주소를 담을 리스트 cur를 초기화한다.

res = []
cur = []

 

s.length가 4보다 작거나 12보다 큰 경우에는 아예 처음부터 가지치기를 해주자.

if len(s) < 4 or len(s) > 12: 
    return res

 

이제 DFS 함수를 만들고, 탐색 중에 발견된 유효 IP 주소를 res에 담으면 된다.

 

dfs()의 base case는 다음과 같다.

만약 남은 dots가 0일때, 즉 모든 dots를 탐색에 사용했을 때 return한다.

이 때, idx == len(s)일 때 s의 모든 숫자가 사용되어 유효한 IP 주소를 만들었다는 뜻이므로, 현재까지의 cur를 res에 담고 return한다.

if dots == 0:
    if idx == len(s):
        res.append(".".join(cur[:]))
        return
    return

 

dfs()의 재귀 부분은 다음과 같다.

s의 일부분을 떼어다가 유효한 정수인지 검사한다.

이 때, 탐색해야할 남은 s가 2개나 1개일 경우, idx + 3은 range를 벗어나므로, range(idx, min(idx + 3, len(s)))여야 한다.

 

만약 유효하다면 cur에 해당 정수를 넣고, DFS를 진행한다.

for i in range(idx, min(idx + 3, len(s))):
    digit = s[idx:i + 1]
    if (dots * 3 < len(s[i:]) or
        (digit[0] == "0" and len(digit) > 1) or
        int(digit) > 255):
        return
                
    cur.append(digit)
    dfs(i + 1, dots - 1)
    cur.pop()

 

전체 코드는 다음과 같다.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        cur = []
        
        # impossible to generate valid IP
        if len(s) < 4 or len(s) > 12: 
            return res
        
        
        def dfs(idx, dots):
            # base case
            if dots == 0:
                if idx == len(s):
                    res.append(".".join(cur[:]))
                    return
                return
            
            for i in range(idx, min(idx + 3, len(s))):
                digit = s[idx:i + 1]
                if (dots * 3 < len(s[i:]) or
                    (digit[0] == "0" and len(digit) > 1) or
                    int(digit) > 255):
                    return
                
                cur.append(digit)
                dfs(i + 1, dots - 1)
                cur.pop()

        dfs(0, 4)
        return res

 

---

Leetcode 93. Restore IP Addresses

https://leetcode.com/problems/restore-ip-addresses/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다