[Leetcode] 93. Restore IP Addresses

Restore IP Addresses - LeetCode

IDEA : O(n³) Brute force로 가능한 ip 분할을 모두 탐색함

s 길이가 3이하 혹은 13이상이면 ""리턴

1단계 1,2,3 분할
2단계 1,2,3 분할
3단계 1,2,3 분할
4단계 3단계에 맞게 ip설정

다음 단계로 넘어갈 때 이전 단계에서 분할한 ip가 맞는지 확인 후 넘어감

class Solution {
public:
    vector<string> restoreIpAddresses(string s) 
    {
        vector<string> ans;
        
        if(s.size() > 12 || s.size() < 4)
            return ans;
        
        int remain; // 한 단계 분할 후 사용할 수 있는 남은 글자수를 저장
        
        string a_ip,b_ip,c_ip,d_ip;
        for(int a=1; a<=3; a++)
        {
            a_ip = s.substr(0,a);
            remain = s.size() - a_ip.size();
            
            if(remain >= 3 && is_able(a_ip))
            {
                for(int b=1; b<=3; b++)
                {
                    b_ip = s.substr(a,b);
                    remain = s.size() - a_ip.size() - b_ip.size();
                
                    if(remain >= 2 && is_able(b_ip))
                    {
                        for(int c=1; c< remain; c++)
                        {
                            c_ip = s.substr(a+b,c);
                            d_ip = s.substr(a+b+c, s.size() - a+b+c);
                            
                            if(is_able(c_ip) && is_able(d_ip))
                                 ans.push_back(a_ip+"."+b_ip+"."+c_ip+"."+d_ip);
                        }
                    }
            
                }
            }
        }
                    

        return ans;                        
    }
    
    bool is_able(string a)
    {
        if(a.size() >= 2 && a[0] == '0') //2자리순데 처음이 0으로 시작하면 안됨
            return false;
        else if(stoi(a) > 255) //ip 허용 범위 초과하면 안됨
            return false;
        return true;
    }
};