LeetCode 93(Restore IP Addresses, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

2. 문제 설명

• 주어진 숫자열을 이용하여 유효한 IP 주소로 복원하는 문제
• IP 주소는 네 개의 정수로 이루어져 있으며, 각 정수는 0에서 255 사이의 값이어야 함
• 이때 각 정수는 0으로 시작하면 안됨.(0은 가능, 01은 불가능, 1은 가능)
• 예시) "25525511135”가 주어졌을 가능한 모든 IP 주소 ["255.255.11.135","255.255.111.35"]를 반환 

3. 처음 풀이

• 전형적인 백트래킹
• 온 점 ‘.’으로 구분된 수를 word 라 하자.
• word의 길이는 1~3이 가능하다.
• 따라서 주어진 s의 앞에서 부터 한 글자, 두 글자, 세 글자를 가져오고 남은 부분에 대해 재귀를 때린다.
• 가져온 word에 대해 유망한지 검사를 한다.
• 길이가 1보다 큰데 처음이 ‘0’이면 leading 0가 있으므로 불가능하여 return
• 값이 255보다 크면 불가능하여 return
• 그 외는 유망하므로 현재 path에 word = s[:i+1]를 추가하고 남은 부분 s[i+1:]에 대하여 재귀를 때린다.
• path에 4개의 word가 담기고 남은 문자열인 없다면 result에 추가하고, 마지막에 result를 반환

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []

        def helper(s, path):
            if len(path) == 4 and s == '':
                result.append('.'.join(path[:]))
                return
            for i in range(min(3, len(s))):
                word = s[:i+1]
                if word[0] == "0" and len(word) > 1:
                    return
                if int(word) > 255:
                    return
                path.append(word)
                helper(s[i+1:], path)
                path.pop()
                
        helper(s, [])

        return result

4. 다른 풀이

• 핵심 로직은 차이가 없으나 valid 함수를 따로 만드는 것이 가독성이 좋다.

class Solution:
    def valid(self, temp: str) -> bool:
        if len(temp) > 3 or len(temp) == 0:
            return False
        if len(temp) > 1 and temp[0] == '0':
            return False
        if len(temp) and int(temp) > 255:
            return False
        return True

    def solve(self, ans, output, ind, s, dots):
        if dots == 3:
            if self.valid(s[ind:]):
                ans.append(output + s[ind:])
            return
        for i in range(ind, min(ind+3, len(s))):
            if self.valid(s[ind:i+1]):
                new_output = output + s[ind:i+1] + '.'
                self.solve(ans, new_output, i+1, s, dots+1)

    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        self.solve(ans, "", 0, s, 0)
        return ans

5. 배운 점

• 백트래킹은 가끔은 쉽게 풀리고 가끔은 너무 어렵다. 백트래킹 주제로 문제를 한번 쭉 풀어볼 필요가 있다.