자바 코딩테스트 강좌, 제곱이 아닌 수 찾기

코딩테스트는 현대 소프트웨어 개발에서 필수적인 부분 중 하나입니다. 특히 자바와 같은 객체지향 언어에서의 알고리즘 문제 해결 능력을 키우는 것은 매우 중요합니다. 이번 강좌에서는 ‘제곱이 아닌 수 찾기’라는 알고리즘 문제를 다뤄보겠습니다. 이 문제는 정수 배열에서 제곱수들을 제외한 나머지 수들을 찾는 것입니다.

문제 설명

주어진 정수 배열에서 제곱수가 아닌 수를 찾는 문제입니다. 제곱수란 어떤 정수를 제곱했을 때 나오는 수를 말하며, 예를 들어 0, 1, 4, 9, 16, ... 등이 있습니다.

입력

정수 N이 주어지며 (1 ≤ N ≤ 10000)
N개의 정수가 포함된 배열이 주어집니다.

출력

배열에서 제곱수가 아닌 정수로 이루어진 새로운 배열을 반환합니다.

문제 해결 전략

이 문제를 해결하기 위해 우리는 다음과 같은 단계를 거칩니다:

배열을 순회하여 각각의 수가 제곱수인지 확인합니다.
제곱수가 아닌 경우 새로운 배열에 추가합니다.
결과 배열을 반환합니다.

제곱수 여부 확인 방법

수 x가 제곱수인지 확인하는 방법은 다음과 같습니다. 먼저 x의 제곱근을 계산한 후, 그 제곱근을 정수로 변환하여 다시 제곱해보는 것입니다. 만약 x와 일치하면 x는 제곱수입니다.

boolean isPerfectSquare(int x) {
        if (x < 0) return false;
        int s = (int) Math.sqrt(x);
        return s * s == x;
}

자바 구현

이제 우리는 이 알고리즘을 자바로 구현해 보겠습니다.

import java.util.ArrayList;
import java.util.List;

public class FindNonPerfectSquares {
    
    public static List<Integer> findNonPerfectSquares(int[] arr) {
        List<Integer> result = new ArrayList<>();

        for (int num : arr) {
            if (!isPerfectSquare(num)) {
                result.add(num);
            }
        }
        
        return result;
    }
    
    private static boolean isPerfectSquare(int x) {
        if (x < 0) return false;
        int s = (int) Math.sqrt(x);
        return s * s == x;
    }

    public static void main(String[] args) {
        int[] inputArray = {1, 2, 3, 4, 5, 9, 10, 15, 16, 20};
        List<Integer> nonPerfectSquares = findNonPerfectSquares(inputArray);
        System.out.println("제곱이 아닌 수들: " + nonPerfectSquares);
    }
}

코드 설명

위의 코드에서는 findNonPerfectSquares라는 메서드를 통해 주어진 배열을 순회합니다. 각 숫자에 대해 isPerfectSquare 메서드를 호출하여 제곱수인 경우는 지나치고, 제곱수가 아닌 경우만 결과 리스트에 추가합니다.

테스트

실제로 이 코드를 실행해 보겠습니다. 위의 main 메서드에서는 테스트 입력 배열을 정의하고, 함수 호출 후 제곱이 아닌 수들의 리스트를 출력합니다.

결과 분석

입력 배열 {1, 2, 3, 4, 5, 9, 10, 15, 16, 20}에서 제곱이 아닌 수들은 {2, 3, 5, 10, 15, 20}입니다. 이는 알고리즘의 정확성을 확인하는 중요한 과정입니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 배열의 수를 한 번만 순회하기 때문입니다. 공간 복잡도는 결과 리스트를 저장하는 데 소요되는 공간 때문이므로 최악의 경우 O(N)이 됩니다.

마무리

이번 강좌에서는 제곱이 아닌 수를 찾는 알고리즘 문제를 다뤄보았습니다. 이 문제를 통해 배열을 순회하며 조건에 따라 값을 추가하는 기본적인 알고리즘 문제 해결 방법을 배울 수 있었습니다. 앞으로 반복적으로 출제되는 수많은 알고리즘 문제들에 대한 준비를 위해 이러한 문제들을 꾸준히 풀어보는 것이 중요합니다.

다음 강좌에서는 더 복잡한 알고리즘 문제를 다루어 보도록 하겠습니다. 감사합니다!