LeetCode - 버전 번호 비교

문제 설명

version1과 version2라는 두 개의 버전 번호가 주어지면 이를 비교하십시오.

버전 번호는 점 '.'으로 결합된 하나 이상의 개정으로 구성됩니다. 각 개정판은 숫자로 구성되며 선행 0을 포함할 수 있습니다. 모든 개정에는 적어도 하나의 문자가 포함됩니다. 리비전은 왼쪽에서 오른쪽으로 인덱스가 0이며 맨 왼쪽 리비전은 리비전 0이고 다음 리비전은 리비전 1입니다. 예를 들어 2.5.33 및 0.1은 유효한 버전 번호입니다.

버전 번호를 비교하려면 개정판을 왼쪽에서 오른쪽 순서로 비교하십시오. 리비전은 선행 0을 무시하고 정수 값을 사용하여 비교됩니다. 이는 개정 1과 001이 동일한 것으로 간주됨을 의미합니다. 버전 번호가 색인에서 개정을 지정하지 않으면 개정을 0으로 처리합니다. 예를 들어 버전 1.0은 개정 0이 동일하지만 개정 1은 각각 0과 1이고 0이므로 버전 1.1보다 낮습니다. < 1.

다음을 반환합니다.

버전1 < 버전2이면 -1을 반환합니다.
버전1 > 버전2이면 1을 반환합니다.
그렇지 않으면 0을 반환합니다.

문제 진술 출처: https://leetcode.com/problems/compare-version-numbers

예 1:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

예 2:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

예 3:

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

제약:

- 1 <= version1.length, version2.length <= 500
- version1 and version2 only contain digits and '.'
- version1 and version2 are valid version numbers.
- All the given revisions in version1 and version2 can be stored in a 32-bit integer.

설명

점 때문에 문자열을 비교할 수 없습니다. 문자열을 탐색하고 숫자 부분을 분리합니다. 숫자 부분이 같으면 다음 숫자 부분을 비교합니다.

이제 알고리즘을 확인해 봅시다.

- set vnum1 = 0, vnum2 = 0

- loop for i = 0, j = 0 && i < version1.length && j < version2.length
  - loop while i < version1.length && version1[i] != '.'
    - set vnum1 = vnum1 * 10 + (version1[i] - '0')
    - increment i++

  - loop while j < version2.length && version2[j] != '.'
    - set vnum2 = vnum2 * 10 + (version2[j] - '0')
    - increment j++

  - if vnum1 > vnum2
    - return 1
  - else if vnum2 > vnum1
    - return -1

  - set vnum1 = 0, vnum2 = 0
  - increment i++
  - increment j++

- for end

- return 0

이 함수의 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다.

C++, Golang 및 Javascript에서 솔루션을 확인합시다.

C++ 솔루션

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int vnum1 = 0, vnum2 = 0;

        for(int i = 0, j = 0; i < version1.length() || j < version2.length();) {
            while(i < version1.length() && version1[i] != '.') {
                vnum1 = vnum1*10 + (version1[i] - '0');
                i++;
            }

            while(j < version2.length() && version2[j] != '.') {
                vnum2 = vnum2*10 + (version2[j] - '0');
                j++;
            }

            if(vnum1 > vnum2) {
                return 1;
            } else if(vnum2 > vnum1) {
                return -1;
            }

            vnum1 = 0;
            vnum2 = 0;
            i++;
            j++;
        }

        return 0;
    }
};

골랑 솔루션

func compareVersion(version1 string, version2 string) int {
    vnum1, vnum2 := 0, 0
    i, j := 0, 0

    for i < len(version1) || j < len(version2) {
        for i < len(version1) && version1[i] != '.' {
            vnum1 = vnum1 * 10 + int(version1[i] - '0')
            i++
        }

        for j < len(version2) && version2[j] != '.' {
            vnum2 = vnum2 * 10 + int(version2[j] - '0')
            j++
        }

        if vnum1 > vnum2 {
            return 1
        } else if vnum2 > vnum1 {
            return -1
        }

        vnum1, vnum2 = 0, 0
        i++
        j++
    }

    return 0;
}

자바스크립트 솔루션

var compareVersion = function(version1, version2) {
    let vnum1 = 0, vnum2 = 0;

    for(let i = 0, j = 0; i < version1.length || j < version2.length;) {
        while(i < version1.length && version1[i] != '.') {
            vnum1 = vnum1 * 10 + parseInt(version1[i] - '0');
            i++;
        }

        while(j < version2.length && version2[j] != '.') {
            vnum2 = vnum2 * 10 + parseInt(version2[j] - '0');
            j++;
        }

        if(vnum1 > vnum2) {
            return 1;
        } else if(vnum2 > vnum1) {
            return -1;
        }

        vnum1 = 0, vnum2 = 0;
        i++;
        j++;
    }

    return 0;
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

Input: version1 = "1.01"
       version2 = "1.001"

Step 1: vnum1 = 0, vnum2 = 0

Step 2: loop for i = 0, j = 0; i < version1.length() || j < version2.length()
          i < version1.length() || j < version2.length()
          0 < 4 || 0 < 5
          true

          loop while i < version1.length() && version1[i] != '.'
            0 < 4 && version1[0] != '.'
            true && '1' != '.'
            true

            vnum1 = vnum1 * 10 + (version1[i] - '0')
                  = 0 * 10 + version1[0] - '0'
                  = 0 + 1
                  = 1

            i++
            i = 1

            i < version1.length() && version1[i] != '.'
            1 < 4 && version1[1] != '.'
            true && '.' != '.'
            false

          loop while j < version2.length() && version2[j] != '.'
            0 < 5 && version2[0] != '.'
            true && '1' != '.'
            true

            vnum1 = vnum1 * 10 + (version2[j] - '0')
                  = 0 * 10 + version2[j] - '0'
                  = 0 + 1
                  = 1

            j++
            j = 1

            if vnum1 > vnum2
              1 > 1
              false
            else if vnum2 > vnum1
              1 > 1
              false

            vnum1 = 0
            vnum2 = 0

            i++
            i = 2

            j++
            j = 2

Step 3: loop for i < version1.length() || j < version2.length()
          i < version1.length() || j < version2.length()
          2 < 4 || 2 < 5
          true

          loop while i < version1.length() && version1[i] != '.'
            2 < 4 && version1[2] != '.'
            true && '0' != '.'
            true

            vnum1 = vnum1 * 10 + (version1[i] - '0')
                  = 0 * 10 + version1[2] - '0'
                  = 0 + 0
                  = 0

            i++
            i = 3

            i < version1.length() && version1[i] != '.'
            3 < 4 && version1[3] != '.'
            true && '1' != '.'
            true

            vnum1 = vnum1 * 10 + (version1[i] - '0')
                  = 0 * 10 + version1[3] - '0'
                  = 0 + 1
                  = 0

            i++
            i = 4

            i < version1.length()
            4 < 4
            false

          loop while j < version2.length() && version2[j] != '.'
            2 < 5 && version2[2] != '.'
            true && '0' != '.'
            true

            vnum2 = vnum2 * 10 + (version2[j] - '0')
                  = 0 * 10 + version2[2] - '0'
                  = 0 + 0
                  = 0

            j++
            j = 3

            j < version2.length() && version2[j] != '.'
            3 < 5 && version2[3] != '.'
            true && '0' != '.'
            true

            vnum2 = vnum2 * 10 + (version2[j] - '0')
                  = 0 * 10 + version2[3] - '0'
                  = 0 + 1
                  = 0

            j++
            j = 4

            j < version2.length() && version2[j] != '.'
            4 < 5 && version2[4] != '.'
            true && '1' != '.'
            true

            vnum2 = vnum2 * 10 + (version2[j] - '0')
                  = 0 * 10 + version2[4] - '0'
                  = 0 + 1
                  = 1

            j++
            j = 5

            j < version2.length()
            5 < 5
            false

            if vnum1 > vnum2
              1 > 1
              false
            else if vnum2 > vnum1
              1 > 1
              false

            vnum1 = 0
            vnum2 = 0

            i++
            i = 5

            j++
            j = 6

Step 4: loop for i < version1.length() || j < version2.length()
          5 < 4 || 6 < 5
          false

Step 5:  return 0

We return the answer as 0.