1317. Convert Integer to the Sum of Two No-Zero Integers

https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers/

Convert Integer to the Sum of Two No-Zero Integers - LeetCode

입력으로 들어오는 n의 값을 두 개의 Integer 합의 값을 찾는 문제로 정수에서는 0 이 포함되지 않아야 한다.

n의 범위는 2 <= n <= 10^4로 임으로 bruth-force로 접근 가능해 보인다.

 

bruth-force 접근

left의 시작 값은 1, right 값은 n - i로 초기화한다.

left와 right의 값에 zero 가 있는지 확인한다.

반복문의 횟수는 N의 절반으로 초기화하였다. left, right의 값이 증가, 감소 함으로 모든 N/2+1 회만 연산이 가능하다. N의 MAX는 10000 임으로 최대 계산량은 10000 / 2 + 1 O(5001) O(n) 이 된다.

class Solution {
public:
    bool checkZero(int n) {
        while (n) {
            int cand = n % 10;
            if (cand == 0) {
                return true;
            }
            n = n / 10;
        }
        return false;
    }
    vector<int> getNoZeroIntegers(int n) {
        vector<int> arr;
        int count = n / 2 + 1;
        for (int i = 1; i < count; i++) {
            int left = i;
            int right = n - i;

            if (checkZero(left) || checkZero(right)) {
                continue;
            }
            arr.push_back(left);
            arr.push_back(right);
            break;
        }

        return arr;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Convert Integer to the Sum of Two No-Zero Integers.

 

string class를 활용한 풀이

정수를 to_string() 이용하여 문자열로 변경하고 find() 함수를 통해 0 문자가 있으면 계속 a의 값을 증가시켜서 확인하는 방법

class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
      int a=1;
      int b;
      while(1){
        b=n-a;
        if (to_string(a).find('0')==string::npos && to_string(b).find('0')==string::npos){
          return {a,b};
        }
        ++a;
      }
    }
};

Runtime: 4 ms, faster than 59.83% of C++ online submissions for Convert Integer to the Sum of Two No-Zero Integers.

 

풀이가 영 석연치는 않지만 string class로 변환하는 비용이 커 보인다. N의 값이 10^4 이 아니라 그이 상일 때도 생각해보자.