자바(Java)로 배열의 모든 자릿수를 활용해 3으로 나누어 떨어지는 수를 만들 수 있는지 확인하는 방법

배열에 포함된 모든 숫자를 사용하여 3으로 나누어 떨어지는 수를 만들 수 있는지 확인하는 문제는 코딩 테스트에서 자주 등장하는 유형입니다. 이 글에서는 자바(Java)를 이용해 이 문제를 간단하게 해결하는 방법을 살펴보겠습니다.

핵심 원리

어떤 수가 3으로 나누어 떨어지려면 그 수의 각 자릿수의 합 역시 3으로 나누어 떨어져야 한다는 수학적 성질이 있습니다. 따라서 배열의 요소들을 하나씩 더하면서 3으로 나눈 나머지만 추적하면, 전체 숫자를 조합했을 때 3의 배수가 되는지 손쉽게 판별할 수 있습니다.

예제 코드

import java.io.*;
import java.util.*;
public class Demo{
   public static boolean division_possible(int my_arr[], int n_val){
      int rem = 0;
      for (int i = 0; i < n_val; i++)
         rem = (rem + my_arr[i]) % 3;
      return (rem == 0);
   }
   public static void main(String[] args){
      int my_arr[] = { 66, 90, 87, 33, 123};
      int n_val = 3;
      if (division_possible(my_arr, n_val))
         System.out.println("It is possible to make a number that can be divided by 3");
      else
         System.out.println("It is not possible to make a number that can be divided by 3");
   }
}

실행 결과

It is possible to make a number that can be divided by 3

코드 설명

위 코드에는 Demo라는 클래스가 정의되어 있으며, 그 안에 division_possible이라는 함수가 포함되어 있습니다. 이 함수는 주어진 숫자들을 조합하여 3으로 나누어 떨어지는 수를 만들 수 있는지 여부를 판별하는 역할을 합니다.

함수 내부에서는 나머지를 저장할 변수 rem을 0으로 초기화한 뒤, 반복문을 통해 배열의 각 요소를 차례대로 더하면서 3으로 나눈 나머지를 계속 갱신합니다. 반복이 끝난 후 rem이 0이면 true를, 그렇지 않으면 false를 반환합니다.

main 함수에서는 실제 값들이 담긴 배열과 검사할 요소의 개수인 n_val 값을 정의합니다. 이후 해당 인수들을 전달하여 함수를 호출하고, 반환된 결과에 따라 3의 배수를 만들 수 있는지에 대한 메시지가 콘솔에 출력됩니다.

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)으로 매우 효율적이며, 추가 메모리 사용 없이 상수 공간(O(1))으로 해결할 수 있다는 장점이 있습니다.