LeetCode - Restore IP Addresses

문제요약

유효한 IP 주소는 . 구분된 4개의 정수로 표현이 된다
각 정수는 0~255 까지의 값을 가질 수 있다
정수 앞에 0은 올 수 없다

예시

1. 입력: s = "25525511135"
   출력: ["255.255.11.135","255.255.111.35"]
2. 입력: s = "0000"
   출력: ["0.0.0.0"]
3. 입력: s = "101023"
   출력: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

풀이

n = 문자열 s의 길이
if(n이 12보다 크다면) return []
if(n이 4보다 작다면) return []

result = []

funtion isVaild(분할된 문자열){
  if(문자열의 길이가 1이고 값이 0인경우) return true
  if(문자열의 시작이 0인경우) return false
  if(문자열의 값이 255보다 작은경우) return true
  return false
}
// 점찍는 위치
for(i1 은 1부터 n-2까지){
  part1 = 문자열 시작부터 i1까지
  isVaild가 false면 continue
  for(i2 는 i1+1부터 n-1까지){
    part2 = 문자열 i1부터 i2까지
    isVaild가 false면 continue
    for(i3 는 i2+1부터 n까지){
      part3 = 문자열 i2부터 i3까지
      isVaild가 false면 continue
      part4 = 문자열 i3부터 끝까지
      isVaild가 false면 continue
      result.push("part1.part2.part3.part4")
      }
    }
return result
}

• 주어진 문자열에 대해 중첩 반복문으로 총 4개의 part를 나눈다
• 각 part를 나눌때 마다 isVaild함수를 실행시켜 반환된 값이 true일때만 진행한다
• 모두 true가 나오면 해당 part를 .으로 구분하여 배열에 삽입힌다

시간복잡도 O(N^3) -> 문자열 분할에 대해 조금 더 공부해보고 줄여야 할 필요가 있다다