2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 5월 3일 (금)
Leetcode daily problem
165. Compare Version Numbers
https://leetcode.com/problems/compare-version-numbers/?envType=daily-question&envId=2024-05-03
Problem
두 개의 버전 번호(version1과 version2)가 주어질 때
- version1 < version2는 -1을 반환
- version1 > version2는 1을 반환
- 둘 다 아니라면 0을 반환한다.
버전 번호는 점 '.'으로 연결된 하나 이상의 개정판으로 구성된다.
각 개정판은 숫자로 구성되며 앞에 0이 포함될 수 있다.
모든 개정에는 최소한 하나의 문자가 포함된다.
개정판은 왼쪽에서 오른쪽으로 0 인덱스로 지정되며 가장 왼쪽 개정판은 개정판 0, 다음 개정판은 개정판 1 등으로 진행된다.
예를 들어 2.5.33과 0.1은 유효한 형식의 버전 번호입니다.
버전 번호를 비교하려면 버전을 왼쪽에서 오른쪽 순서로 비교한다.
개정판은 선행 0을 무시하고 정수 값을 사용하여 비교한다.
즉 개정 1과 001이 동일한 것으로 간주됨을 의미한다.
버전 번호가 인덱스에서 개정을 지정하지 않으면 개정을 0으로 처리한다.
예를 들어 버전 1.0, 1.1은 1.1이 버전이 더 높고,
1.01과 1.001은 둘다 01, 001은 같은 버전 1을 의미한다.
Solution
greedy algorithm (그리디 알고리즘)
각 단계에서 가장 최적의 선택을 하는데, 이 경우에는 각 부분을 순서대로 비교하여 가장 최적의 선택을 하고, 그 결과에 따라 비교를 진행한다.
먼저 입력된 두 버전 문자열을 점(.)을 기준으로 나누어 각 부분을 리스트에 저장한다.두 버전 중에서 길이가 더 긴 리스트의 길이를 기준으로 반복문을 돌면서 각 부분을 비교한다.
길이가 더 짧은 부분은 0으로 채워 비교하는데,
만약 비교 중에 한 버전의 부분이 더 작은 경우에는 -1을 반환하고, 더 큰 경우에는 1을 반환한다.
모든 부분을 비교한 후에도 동일하다면 0을 반환하면 된다.
Code
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
v1_list = version1.split('.')
v2_list = version2.split('.')
length = max(len(v2_list), len(v1_list))
for i in range(length):
v1 = int(v1_list[i]) if i < len(v1_list) else 0
v2 = int(v2_list[i]) if i < len(v2_list) else 0
if v1 < v2:
return -1
elif v1 > v2:
return 1
return 0 Complexicity
시간 복잡도
각 버전의 부분을 비교하는데 선형 시간이 걸리기 때문에 시간 복잡도는 O(max(N, M))이다. N은 첫 번째 버전의 부분 개수이고, M은 두 번째 버전의 부분 개수이다.
공간 복잡도
입력으로 받은 두 버전을 나누어 저장하는데 필요한 리스트의 크기와 관련이 있고, 두 버전 중에서 더 긴 버전의 부분 수에 비례하여 공간을 사용하므로, 공간 복잡도는 O(max(N, M))이다.
