[LeetCode] - 2169. Count Operations to Obtain Zero

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Count Operations to Obtain Zero" 문제입니다.

--> https://leetcode.com/problems/count-operations-to-obtain-zero/description/

 

문제 : 

You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

 

For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4.

However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

---

Example 1 :

Input : num1 = 2, num2 = 3

Output : 3

Explanation :

- Operation 1 : num1 = 2, num2 = 3.

Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.

- Operation 2 : num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.

- Operation 3 : num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.

Now num1 = 0 and num2 = 1.

Since num1 == 0, we do not need to perform any further operations.

So the total number of operations required is 3.

 

Example 2 :

Input : num1 = 10, num2 = 10

Output : 1

Explanation :

- Operation 1 : num1 = 10, num2 = 10.

Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.

Now num1 = 0 and num2 = 10.

Since num1 == 0, we are done.

So the total number of operations required is 1.

 

Constraints : 0 <= num1, num2 <= 10^5

---

이 문제는 주어진 두 비음수 정수 num1과 num2에 대해 한 수가 0이 될 때까지 연산을 반복하여 연산 횟수를 반환하는 문제입니다. 연산은 다음과 같이 수행됩니다:

• num1 >= num2일 때, num1에서 num2를 뺍니다.
• num1 < num2일 때, num2에서 num1을 뺍니다.

class Solution {
    public int countOperations(int num1, int num2) {
        int count = 0;
        while (num1 != 0 && num2 != 0) {
            if (num1 >= num2) {
                num1 = num1 - num2;
                count++;
            } else {
                num2 = num2 - num1;
                count++;
            }
        }

        return count++;
        
    }
}

 

이번 문제는 사실상 큰 어려움 없이 해결해갈 수 있는 문제라고 슬쩍 평가해 봅니다. 문제를 잘 이해했으면 바로 이 코드가 딱 생각날 겁니다. 주어진 조건들을 조건문으로만 잘 번역하신다면 풀 수 있습니다. 그래도 상세한 설명을 드리자면 : 

1. 변수 초기화 :
   • count 변수를 0으로 초기화합니다. 이 변수는 총 연산 횟수를 기록합니다.
2. 반복문 :
   • num1 또는 num2 중 하나가 0이 될 때까지 반복합니다.
   • num1이 num2보다 크거나 같으면 num1에서 num2를 빼고 count를 1 증가시킵니다.
   • 그렇지 않으면 num2에서 num1을 빼고 count를 1 증가시킵니다.
3. 결과 반환 :
   • 모든 연산이 끝난 후 count 값을 반환합니다.

• 시간 복잡도: O(max(num1, num2))
  • 최악의 경우, 반복문은 두 수 중 큰 값만큼 반복됩니다. 각 반복마다 두 수 중 하나는 줄어들기 때문입니다.
  • 각 반복에서 한 번의 뺄셈 연산이 수행되므로, 총 연산 횟수는 두 수 중 큰 값에 비례합니다.
• 공간 복잡도: O(1)
  • 추가적인 배열이나 리스트를 사용하지 않으며, 상수 공간만 사용합니다. count와 num1, num2만 사용되므로 공간 복잡도는 O(1)입니다.

이로써, 아주 효율적인 코드가 나옵니다. 사실 저는 제 코드가 Beats 100 %일 줄 알았는데, 누군가가 더 나은 퍼포먼스를 했더군요. 보니까 제 코드랑 진짜 거의 똑같지만 확연한 차이가 하나 있습니다. 바로 보시죠

---

class Solution {
    public int countOperations(int num1, int num2) {
        int count=0;
        while(num1!=0 && num2!=0){
            if(num1<num2){
                count+=num2/num1;
                num2=num2%num1;
            }else{
                count+=num1/num2;
                num1=num1%num2;
            }
        }
        return count;
    }
}

// abanoubcs 유저의 코드

 

이 사람 코드를 보시면, count 하는 법과, num1,2 들을 다루는 식이 조금 달라보입니다. 모듈로를 쓰고, 나누고... 왜 그런지 궁금해서 구글링 좀 해봤습니다. 

1. 한 번의 반복에서 여러 번의 뺄셈을 수행 :
   • 이전 코드에서는 한 번의 반복에서 한 번의 뺄셈만 수행했습니다.
   • 이 코드에서는 num1이나 num2가 다른 수로 나눠질 수 있는 만큼 한 번에 여러 번의 뺄셈을 수행합니다. 예를 들어, num1 = 10이고 num2 = 2일 때, 이전 코드에서는 num1에서 num2를 한 번에 하나씩 빼는 방식으로 5번의 연산이 필요하지만, 이 코드는 10 / 2 = 5를 한 번에 계산하여 연산 횟수를 최적화합니다.

고로, 이 분은 저보다 기초적인 수학 개념을 잘 응용함으로써, 저보다 우위에 있었던 것입니다. 정말 간단한 로직인데, 왜 이걸 생각 못했을까 싶습니다. 아니면, 애초에도 이 방법을 절대 못 떠올렸었을 것입니다. 이래서 컴공에서도 수학이 중요하다라는 것을 자잘하게 깨달을 때도 있네요

 

--> 최적화된 연산 

• 나눗셈과 나머지 연산을 사용하여 연산 횟수를 줄입니다.
• 이 최적화는 반복 횟수를 크게 줄여줄 수 있습니다.

시간, 공간 복잡도는 그래도 여전히 제 코드와 같습니다. 정말로 저런 코드 센스 몇 개 차이가 95% 100% 차이를 내네요. 분발해야겠습니다.

---

내 코드, 다른 유저 코드 Runtime 결과

•