버전 번호 비교 문제란?
두 개의 버전 문자열 version1과 version2를 비교하는 프로그램을 작성해야 한다고 가정해 보겠습니다. 비교 결과는 다음과 같이 반환합니다.
- version1 > version2이면
1반환 - version1 < version2이면
-1반환 - 두 버전이 같으면
0반환
여기서 버전 문자열은 비어 있지 않으며, 숫자와 점(.) 문자만 포함한다고 가정할 수 있습니다. 주의할 점은 점(.)이 소수점을 의미하지 않는다는 것입니다. 점은 단순히 숫자 시퀀스를 구분하는 구분자 역할만 합니다.
예를 들어 버전 2.5는 "2와 반"이 아닙니다. 첫 번째 레벨 수정판 2의 다섯 번째 두 번째 레벨 수정판을 의미합니다.
기본 수정 번호 규칙
각 레벨의 기본 수정 번호는 0으로 간주합니다. 예를 들어 버전 3.4는 첫 번째 레벨 수정 번호가 3, 두 번째 레벨 수정 번호가 4이며, 세 번째와 네 번째 레벨 수정 번호는 모두 0입니다.
따라서 입력이 version1 = "1.0.1", version2 = "1"이라면 결과는 +1이 됩니다. 세 번째 레벨에서 1이 0보다 크기 때문입니다.
해결 알고리즘
다음 단계를 따라 문제를 해결할 수 있습니다.
version1_arr: version1을 점(.)으로 분리해 만든 정수 배열version2_arr: version2를 점(.)으로 분리해 만든 정수 배열- i를 0부터 두 배열 길이 중 더 큰 값까지 반복:
- v1 := i가 version1_arr의 길이보다 작으면 version1_arr[i], 그렇지 않으면 0
- v2 := i가 version2_arr의 길이보다 작으면 version2_arr[i], 그렇지 않으면 0
- v1 > v2이면 1 반환, v1 < v2이면 -1 반환
- 반복이 모두 끝나면 0 반환 (두 버전이 동일)
핵심 아이디어는 짧은 버전 문자열에 대해 존재하지 않는 자릿수를 0으로 채워 처리하는 것입니다. 이렇게 하면 "1.0.1"과 "1.0.1.0"처럼 표기 방식만 다른 사실상 동일한 버전도 올바르게 비교할 수 있습니다.
파이썬 구현 예제
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
class Solution:
def compareVersion(self, version1, version2):
versions1 = [int(v) for v in version1.split(".")]
versions2 = [int(v) for v in version2.split(".")]
for i in range(max(len(versions1), len(versions2))):
v1 = versions1[i] if i < len(versions1) else 0
v2 = versions2[i] if i < len(versions2) else 0
if v1 > v2:
return 1
elif v1 < v2:
return -1
return 0
ob1 = Solution()
print(ob1.compareVersion("1.0.1", "1.0"))
입력
"1.0.1"
"1.0"
출력
1
코드 설명
먼저 split(".") 메서드로 버전 문자열을 점 기준으로 나눈 뒤, 리스트 컴프리헨션으로 각 조각을 정수로 변환합니다. 이후 두 배열 중 더 긴 길이만큼 반복하면서 자릿수별로 값을 비교합니다.
인덱스가 배열 범위를 벗어나면 해당 버전의 자릿수를 0으로 간주하므로, 길이가 다른 버전 문자열도 안전하게 비교됩니다. 첫 번째로 크기 차이가 발견되는 자릿수에서 즉시 1 또는 -1을 반환하고, 모든 자릿수가 같다면 최종적으로 0을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n + m)입니다(n, m은 각 버전 문자열의 길이). 공간 복잡도 역시 O(n + m)으로, 버전 문자열을 저장하는 배열에 비례합니다.