Skip to main content

37. [Java] 1로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/181880

  • 정수 n이 있을 때, 1이 될 때까지 다음을 반복한다
    • 짝수면: n = n / 2
    • 홀수면: n = (n - 1) / 2
  • 즉, 모든 수를 1이 될 때까지 반으로 나누는 연산 횟수 return
  • 3 ≤ num_list의 길이 ≤ 15
  • 1 ≤ num_list의 원소 ≤ 30

정답코드

class Solution {
    public int solution(int[] num_list) {
        int count = 0;

        for (int num : num_list) {
            while (num > 1) {
                num /= 2;
                count++;
            }
        }

        return count;
    }
}

이 문제를 가장 간단하게 풀 수 있는 방법이다.

  • while (num > 1) 이 반복 조건
  • num /= 2 하며 count++
  • break는 굳이 쓰지 않아도 while 조건으로 충분히 종료된다.

정수 n이 있을 때, 1이 될 때까지 다음을 반복한다.

  • 짝수면: n = n / 2
  • 홀수면: n = (n - 1) / 2 → 사실상 n = n / 2로 같음 ((n - 1) / 2 = n / 2 (정수 나눗셈에서))
  • 짝수든 홀수든 결국은 / 2 연산을 한 번 하게 되기 때문에 이 과정을 1이 될 때까지 반복하면 된다.
  • 즉, 홀수 짝수 구분해서 분기점을 만들지 않고, 배열 안에 있는 모든 수를 1이 될 때까지 반으로 나누는 연산 횟수를 구하면 된다.

오답은 아니지만 내가 푼 코드

class Solution {
    public int solution(int[] num_list) {
        int cnt = 0;
        
        while (true) {
            boolean allOne = true;
            
            for (int i = 0; i < num_list.length; i++) {
                if (num_list[i] > 1) {
                    allOne = false; // 아직 배열에 1이 아닌 원소가 있음
                    if (num_list[i] % 2 == 0) {
                        num_list[i] /= 2;
                    } else {
                        num_list[i] = (num_list[i] - 1) / 2;
                    }
                    cnt++; 
                }
            }
            if (allOne) break;
        } 
        return cnt;
    }
}

내가 짠 코드는 배열 전체를 동시에 반복 처리하는 방식이다.
while (true) 을 돌려서 배열의 모든 요소가 1이 될 때까지 반복하면서 cnt++ 하다가 모든 요소가 1이 되면 break;로 반복문을 종료한다.
while, break, boolean 상태 판단 등 논리 흐름 연습에 좋지만 모든 원소를 매번 검사하므로 반복 횟수가 많아져서 비효율적이다.

반면, 맨 위에서 제시한 정답 코드는 가장 최적의 방식이다. 이 코드는 배열의 각 원소를 개별적으로 처리하며, for + while 구조를 통해 각 숫자가 1이 될 때까지 나누기 연산을 반복하면서 카운트를 누적한다. 이 문제의 제한사항에서는 num_list의 크기가 최대 15로 작기 때문에 두 방식 모두 정답은 맞지만, 만약 num_list가 1,000개이고 그중 대부분이 큰 수라면, 내가 처음에 짰던 전체 반복 구조의 코드는 while 루프를 수십 번, 수백 번 더 돌게 되어 비효율적이다. 반면, 개별 처리는 필요한 연산만 정확히 수행하므로 속도 면에서 더 우수하고 안정적이다. 따라서 이 문제는 개별적으로 처리하는 방식이 성능과 유지보수 측면 모두에서 더 나은 선택이다.


Back to top