Java 배열에서 중복 요소 확인하는 방법

소개

이 랩에서는 Java 에서 다양한 접근 방식을 사용하여 배열에 중복된 요소가 있는지 확인하는 방법을 배우게 됩니다. 비교 과정을 명확하게 이해할 수 있는 중첩 루프를 사용하는 기본적인 방법부터 시작합니다.

다음으로, 더 빠른 중복 감지를 위해 Java 컬렉션을 활용하는 방법을 보여주는 HashSet 데이터 구조를 활용하는 보다 효율적인 기술을 살펴보겠습니다. 마지막으로, 배열을 정렬하는 것이 중복 식별 프로세스를 어떻게 단순화할 수 있는지 살펴보겠습니다. 이 랩을 마치면 Java 배열에서 중복 요소를 처리하기 위한 여러 가지 전략을 갖추게 될 것입니다.

중첩 루프를 사용하여 중복 확인

이 단계에서는 Java 에서 중첩 루프를 사용하여 배열 내에서 중복 요소를 찾는 기본적인 접근 방식을 살펴보겠습니다. 이 방법은 이해하기 쉽고 간단하여 배열 조작 및 기본 알고리즘 설계를 배우는 데 좋은 시작점입니다.

먼저, ~/project 디렉토리에 FindDuplicatesNested.java라는 새 Java 파일을 생성해 보겠습니다. WebIDE 파일 탐색기에서 project 폴더를 마우스 오른쪽 버튼으로 클릭하고 "New File"을 선택한 다음 이름을 입력하여 직접 수행할 수 있습니다.

이제 코드 편집기에서 FindDuplicatesNested.java 파일을 열고 다음 Java 코드를 추가합니다.

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

이 코드를 자세히 살펴보겠습니다.

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};: 이 줄은 numbers라는 정수 배열을 선언하고 중복을 포함한 일부 값으로 초기화합니다.
• for (int i = 0; i < numbers.length; i++): 이것은 외부 루프입니다. 인덱스 i를 사용하여 배열의 각 요소를 반복합니다.
• for (int j = i + 1; j < numbers.length; j++): 이것은 내부 루프입니다. 인덱스 i의 각 요소에 대해, 인덱스 i 다음 요소부터 시작하여 배열의 나머지 요소를 반복합니다. 이는 요소를 자체와 비교하는 것을 방지하고 동일한 중복 쌍을 두 번 찾는 것을 방지하는 데 중요합니다 (예: 인덱스 1 을 인덱스 4 와 비교한 다음 인덱스 4 를 인덱스 1 과 비교).
• if (numbers[i] == numbers[j]): 이 조건은 인덱스 i의 요소가 인덱스 j의 요소와 같은지 확인합니다. 같으면 중복을 찾은 것입니다.
• System.out.println("Duplicate found: " + numbers[j]);: 중복이 발견되면 이 줄은 중복 요소를 나타내는 메시지를 출력합니다.

Ctrl + S (macOS 에서는 Cmd + S) 를 눌러 파일을 저장합니다.

이제 WebIDE 하단의 터미널을 엽니다. ~/project 디렉토리에 있는지 확인합니다. pwd를 입력하고 Enter 키를 눌러 확인할 수 있습니다. 출력은 /home/labex/project여야 합니다.

javac 명령을 사용하여 Java 코드를 컴파일합니다.

javac FindDuplicatesNested.java

오류가 없으면 컴파일이 성공하고 FindDuplicatesNested.class 파일이 ~/project 디렉토리에 생성됩니다. ls를 입력하고 Enter 키를 눌러 확인할 수 있습니다.

마지막으로, java 명령을 사용하여 컴파일된 Java 프로그램을 실행합니다.

java FindDuplicatesNested

프로그램에서 찾은 중복 요소를 나타내는 출력을 볼 수 있습니다.

이 중첩 루프 접근 방식은 배열의 모든 가능한 요소 쌍을 비교하여 작동합니다. 이해하기는 쉽지만 매우 큰 배열의 경우 비효율적일 수 있습니다. 다음 단계에서는 중복을 찾는 보다 효율적인 방법을 살펴보겠습니다.

HashSet 을 사용하여 효율적인 중복 확인

이전 단계에서는 중복을 찾기 위해 중첩 루프를 사용했는데, 이는 간단하지만 큰 배열의 경우 속도가 느릴 수 있습니다. 이 단계에서는 HashSet을 사용하여 중복을 찾는 보다 효율적인 방법을 배우겠습니다.

HashSet은 고유한 요소를 저장하는 Java 의 컬렉션입니다. 즉, HashSet에 이미 있는 요소를 추가하려고 하면 추가 작업이 실패합니다 (또는 false를 반환합니다). 이 속성을 활용하여 중복을 효율적으로 감지할 수 있습니다.

아이디어는 다음과 같습니다. 배열을 반복하고 각 요소에 대해 HashSet에 추가하려고 시도합니다. add() 메서드가 false를 반환하면 해당 요소가 이미 집합에 있다는 의미이므로 중복입니다.

~/project 디렉토리에 FindDuplicatesHashSet.java라는 새 Java 파일을 생성해 보겠습니다.

코드 편집기에서 FindDuplicatesHashSet.java 파일을 열고 다음 Java 코드를 추가합니다.

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

이 코드의 새로운 부분을 살펴보겠습니다.

• import java.util.HashSet; 및 import java.util.Set;: 이 줄은 HashSet을 사용하기 위해 필요한 클래스를 가져옵니다.
• Set<Integer> uniqueElements = new HashSet<>();: 이 줄은 Integer 객체를 저장할 빈 HashSet을 생성합니다. HashSet이 Set 인터페이스를 구현하므로 유형으로 Set을 사용합니다.
• for (int number : numbers): 이것은 향상된 for 루프 (for-each 루프라고도 함) 로, numbers 배열의 각 요소를 반복하는 편리한 방법입니다.
• !uniqueElements.add(number): 이것이 핵심 로직입니다. uniqueElements.add(number)는 현재 number를 HashSet에 추가하려고 시도합니다. 숫자가 이미 있으면 add()는 false를 반환합니다. ! 연산자는 이 결과를 부정하므로 if 조건은 add()가 false를 반환할 때만 true 가 되어 중복을 나타냅니다.

파일을 저장합니다 (Ctrl + S 또는 Cmd + S).

이제 터미널에서 Java 코드를 컴파일합니다.

javac FindDuplicatesHashSet.java

컴파일이 성공하면 프로그램을 실행합니다.

java FindDuplicatesHashSet

HashSet 메서드를 사용하여 찾은 중복 요소를 나열하는 출력을 볼 수 있습니다. 이 방법은 특히 큰 배열의 경우 중첩 루프 접근 방식보다 일반적으로 빠릅니다. 이는 HashSet에서 요소를 추가하고 확인하는 것이 매우 효율적이기 때문입니다.

정렬된 배열로 테스트

이 마지막 단계에서는 중복을 찾는 또 다른 접근 방식을 탐구할 것입니다. 특히 배열이 정렬된 경우에 해당합니다. 배열이 정렬된 경우 중복 요소는 항상 서로 인접하게 됩니다. 이를 통해 인접한 요소만 비교하여 중복을 찾는 매우 간단하고 효율적인 방법이 가능합니다.

먼저, ~/project 디렉토리에 FindDuplicatesSorted.java라는 새 Java 파일을 생성해 보겠습니다.

코드 편집기에서 FindDuplicatesSorted.java 파일을 열고 다음 Java 코드를 추가합니다.

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

이 코드의 주요 부분을 살펴보겠습니다.

• import java.util.Arrays;: 이 줄은 정렬을 포함하여 배열에 대한 유틸리티 메서드를 제공하는 Arrays 클래스를 가져옵니다.
• Arrays.sort(numbers);: 이 줄은 numbers 배열을 오름차순으로 정렬합니다.
• for (int i = 0; i < numbers.length - 1; i++): 이 루프는 정렬된 배열을 반복합니다. 현재 요소 (numbers[i]) 를 다음 요소 (numbers[i + 1]) 와 비교하므로 numbers.length - 1까지 루프합니다.
• if (numbers[i] == numbers[i + 1]): 이 조건은 현재 요소가 다음 요소와 같은지 확인합니다. 같으면 중복을 찾은 것입니다.

파일을 저장합니다 (Ctrl + S 또는 Cmd + S).

이제 터미널에서 Java 코드를 컴파일합니다.

javac FindDuplicatesSorted.java

컴파일이 성공하면 프로그램을 실행합니다.

java FindDuplicatesSorted

찾은 중복 요소를 나열하는 출력을 볼 수 있습니다. 배열이 정렬되어 있으므로 중복이 출력에 연속적으로 나타납니다.

이 방법은 정렬된 배열에 매우 효율적입니다. 정렬 후 배열을 한 번만 통과하면 되기 때문입니다. 그러나 초기 정렬 단계 자체에는 시간 비용이 있으며, 이는 Arrays.sort()에서 사용하는 정렬 알고리즘에 따라 달라집니다. int와 같은 기본 유형의 경우 Java 의 Arrays.sort()는 이중 피벗 퀵 정렬을 사용하며, 평균 시간 복잡도는 O(n log n) 입니다.

이제 Java 에서 중첩 루프 사용, HashSet 사용, 정렬된 배열 사용 등 세 가지 다른 방법으로 중복을 찾는 방법을 살펴보았습니다. 각 방법은 단순성, 효율성 및 요구 사항 (배열이 정렬되는 것과 같은) 측면에서 고유한 장단점을 가지고 있습니다. 이러한 다양한 접근 방식을 이해하는 것은 주어진 문제에 가장 적합한 방법을 선택하는 데 유용합니다.

요약

이 Lab 에서는 Java 에서 배열에 중복 요소가 포함되어 있는지 확인하는 다양한 방법을 살펴보았습니다. 먼저, 각 요소를 배열의 다른 모든 요소와 비교하는 중첩 루프를 사용하여 간단한 접근 방식을 구현했습니다. 이 방법은 이해하기 쉽지만 시간 복잡도가 O(n^2) 이므로 큰 배열의 경우 효율성이 떨어집니다.

다음으로, 보다 효율적인 중복 검사를 위해 HashSet 데이터 구조를 활용하는 방법을 배웠습니다. 배열을 반복하고 각 요소를 HashSet에 추가하려고 시도함으로써, 요소가 이미 존재하는 경우 HashSet의 add() 메서드가 false를 반환하므로 요소가 중복인지 빠르게 확인할 수 있습니다. 이 접근 방식은 평균적으로 일반적으로 O(n) 으로 시간 복잡도를 상당히 개선합니다. 마지막으로, 배열을 먼저 정렬하는 것이 정렬 후 중복 요소가 인접하게 되므로 중복을 효율적으로 찾는 데 어떻게 사용될 수 있는지 고려했습니다.