LeetCode 93. Restore IP Addresses

IP 주소로 가능한 모든 경우의 수를 구해야 한다. -> 백트래킹

 

일단 길이가 4보다 작거나 12보다 크면 IP 주소를 만들수조차 없으므로 빈 배열을 반환하게 했다.

또한 조건에서 string에 속할 수 있는 것은 숫자뿐이므로 문자열 -> 숫자 변환은 parseInt(x) 또는 Number(x)를 이용한다.

 

backtracking 함수에서 탈출조건은 배열의 현재 길이가 4일 때 join으로 합쳐서 정답 배열에 푸쉬한 후 탈출하기로 했다. 또한 탈출조건으로 현재 배열이 3개이고 남은 문자열의 길이가 3이상이라면 적절한 IP 주소를 만들 수 없으므로 제거하는 베이스케이스를 추가했다.

 

그 후에는 전형적인 백트래킹을 활용했다. 풀이는 아래와 같다. 

 

const restoreIpAddresses = (s) => {
  if (s.length < 4 || s.length > 12) {
    return [] // 4 보다 길이가 작으면 빈 배열 반환
  }

  const ans = [] // 정답 배열 선언
  const backtracking = (curr = [], index = 0) => {
    if (curr.length === 4) {
      ans.push(curr.join(".")) // 베이스 케이스 4개 다차면 ans에 추가
      return
    }

    if (curr.length === 3 && s.length - index > 3) {
      return
    }

    for (let i = 1; i <= 3; i++) {
      if (s[index] === "0") {
        backtracking([...curr, "0"], index + 1)
        break
      }

      if (Number(s[index]) >= 1 && Number(s[index]) <= 9) {
        if (Number(s.slice(index, index + i)) > 255) {
          break
        }

        curr.push(s.slice(index, index + i))
        backtracking(curr, index + i)
        curr.pop()
      }
    }
  }

  backtracking()
  return [...new Set(ans.filter((e) => e.length === s.length + 3))]
}

 

마지막에 Set 자료구조를 사용해서 반복을 제거해줘야한다. (백트래킹 하다보면 공통된 것이 있을 수 있음)