숫자로만 구성된 문자열이 하나 주어졌을 때, 이 문자열에서 만들어낼 수 있는 모든 유효한 IPv4 주소 조합을 찾아내는 것이 이번 문제의 목표입니다.
접근 방법은 단순합니다. 먼저 문자열의 길이를 확인한 뒤, 점(.) 세 개를 서로 다른 위치에 삽입해 문자열을 네 개의 구간(W, X, Y, Z)으로 나눕니다. 그다음 각 구간이 0~255 범위 안의 숫자인지, 그리고 값이 0이 아닌데 앞에 0이 붙어 있지는 않은지(예: "011") 검사하여 유효한 조합만 골라냅니다.
예시
입력 : "255011123222"
→ 유효한 IP 주소가 아닙니다. ("011"처럼 앞에 0이 붙은 구간은 허용되지 않음)
입력 : "25525522134"
→ 유효한 IP 주소 : 255.255.22.134, 255.255.221.34
알고리즘
1단계: 먼저 문자열의 길이를 확인합니다. 2단계: 문자열에 점 3개를 배치해 네 부분으로 나눕니다. W, X, Y, Z는 각각 0~255 범위의 숫자여야 하며, 값 자체가 0인 경우를 제외하고 앞에 0이 붙을 수 없습니다. 3단계: 점 위치에 대한 다양한 조합을 생성합니다. 4단계: 각 조합이 유효한 IP 주소인지 검사합니다.
예제 코드
# 유효한 IP 주소 후보를 검사하는 파이썬 코드
# IP를 구성하는 각 숫자(구간)가 유효한지 확인하는 함수
def ipvalid(ip):
# "."을 기준으로 분할
ip = ip.split(".")
# 예외 상황(코너 케이스) 검사
for i in ip:
if len(i) > 3 or int(i) < 0 or int(i) > 255:
return False
if len(i) > 1 and int(i) == 0:
return False
if len(i) > 1 and int(i) != 0 and i[0] == '0':
return False
return True
# 문자열을 IP 주소로 변환하는 함수
def ipconvert(A):
con = len(A)
# 문자열 길이 검사
if con > 12:
return []
newip = A
l = []
# 점 위치의 다양한 조합 생성
for i in range(1, con - 2):
for j in range(i + 1, con - 1):
for k in range(j + 1, con):
newip = newip[:k] + "." + newip[k:]
newip = newip[:j] + "." + newip[j:]
newip = newip[:i] + "." + newip[i:]
# 조합의 유효성 검사
if ipvalid(newip):
l.append(newip)
newip = A
return l
# 드라이버 코드
A = input('IP 주소를 입력하세요: ')
print(ipconvert(A))
코드 설명
- ipvalid() 함수는 점으로 분리된 각 구간이 세 자리 이하이고 0~255 범위에 속하는지 확인합니다. 또한 두 자리 이상인데 값이 0이거나, 첫 글자가 '0'으로 시작하는 경우도 유효하지 않다고 판별합니다.
- ipconvert() 함수는 입력 문자열의 길이가 12를 초과하면 즉시 빈 리스트를 반환합니다. IPv4 주소의 숫자 부분은 "xxx.xxx.xxx.xxx" 형태로 최대 12자리이기 때문입니다.
- 세 개의 중첩 반복문으로 점을 삽입할 위치의 모든 조합을 시도합니다. 이때 인덱스가 큰 위치(k, j)부터 먼저 삽입해야 앞서 계산한 인덱스가 밀리지 않으므로 삽입 순서가 중요합니다.
- 유효한 조합만 결과 리스트에 추가되며, 문자열 길이가 최대 12로 제한되므로 삼중 반복문을 사용해도 충분히 빠르게 동작합니다.
실행 결과
Enter IP address25525522134 ['255.255.22.134', '255.255.221.34']