[Programmers] #181880 - 1로 만들기 [Java][C++][Python]

문제 링크

---

1. 아이디어

홀수 x에서 1을 뺀 뒤 2로 나누는 연산은 정수 나눗셈 $\lfloor x / 2 \rfloor$와 결과가 같다. 짝수는 그냥 2로 나누므로, 결국 짝수·홀수를 구분할 필요 없이 각 원소를 1이 될 때까지 2로 나누며 횟수를 세고 모두 합하면 된다. 한 원소당 연산 횟수는 $\lfloor \log_2 x \rfloor$이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log V)$	$O(1)$

($N$ = num_list의 길이, $V$ = 원소의 최댓값)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[] num_list) {
        int cnt = 0;
        for (int x : num_list) {
            while (x > 1) {
                x /= 2;
                cnt++;
            }
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> num_list) {
    int cnt = 0;
    for (int x : num_list) {
        while (x > 1) {
            x /= 2;
            cnt++;
        }
    }

    return cnt;
}

def solution(num_list):
    cnt = 0
    for x in num_list:
        while x > 1:
            x //= 2
            cnt += 1

    return cnt

---