이 문서에서는 Java의 스택에서 중복 요소를 제거하는 두 가지 방법을 살펴보겠습니다. 중첩 루프를 사용한 간단한 접근 방식과 HashSet을 사용하는 보다 효율적인 방법을 비교해 보겠습니다. 목표는 중복 제거를 최적화하는 방법을 보여주고 각 접근 방식의 성능을 평가하는 것입니다.

문제 설명

스택에서 중복된 요소를 제거하는 Java 프로그램을 작성하세요.

입력

Stack data = initData(10L);

산출

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

주어진 스택에서 중복 항목을 제거하려면 2가지 접근 방식이 있습니다. -

• 순진한 접근 방식: 두 개의 중첩 루프를 만들어 어떤 요소가 이미 존재하는지 확인하고 해당 요소가 결과 스택 반환에 추가되지 않도록 합니다.
• HashSet 접근 방식: Set을 사용하여 고유한 요소를 저장하고 O(1) 복잡성을 활용하여 요소가 있는지 여부를 확인합니다.

임의 스택 생성 및 복제

아래는 Java 프로그램이 먼저 임의의 스택을 구축한 다음 추가 사용을 위해 복제본을 생성하는 것입니다. -

private static Stack initData(Long size) {
    Stack stack = new Stack  ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i  manualCloneStack(Stack  stack) {
    Stack  newStack = new Stack  ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

initData 는 지정된 크기와 1~100 범위의 임의 요소로 스택을 생성하는 데 도움이 됩니다.

manualCloneStack 는 다른 스택에서 데이터를 복사하여 데이터를 생성하고 이를 두 아이디어 간의 성능 비교에 사용하는 데 도움이 됩니다.

순진한 접근 방식을 사용하여 특정 스택에서 중복 항목 제거

다음은 Naïve 접근 방식을 사용하여 특정 스택에서 중복 항목을 제거하는 단계입니다. -

• 타이머를 시작합니다.
• 고유한 요소를 저장할 빈 스택을 만듭니다.
• while 루프를 사용하여 반복하고 원래 스택이 비어 있을 때까지 계속해서 최상위 요소를 팝합니다.
• 요소가 이미 결과 스택에 있는지 확인하려면 resultStack.contains(element)를 사용하여 중복 항목을 확인하세요.
• 요소가 결과 스택에 없으면 결과 스택에 추가합니다.
• 종료 시간을 기록하고 소요된 총 시간을 계산합니다.
• 결과 반환

예

다음은 Naïve 접근 방식을 사용하여 주어진 스택에서 중복 항목을 제거하는 Java 프로그램입니다. -

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack  ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

순진한 접근 방식에는

while (!stack.isEmpty())

resultStack.contains(element)

최적화된 접근 방식(HashSet)을 사용하여 지정된 스택에서 중복 항목을 제거합니다.

다음은 최적화된 접근 방식을 사용하여 특정 스택에서 중복 항목을 제거하는 단계입니다. -

• 타이머 시작
• 본 요소를 추적하기 위한 세트를 만듭니다(O(1) 복잡성 검사의 경우).
• 고유한 요소를 저장하기 위한 임시 스택을 만듭니다.
• 스택이 빌 때까지 while 루프를 사용하여 반복합니다.
• 스택에서 최상위 요소를 제거합니다.
• 중복을 확인하기 위해 seen.contains(element)를 사용하여 요소가 이미 세트에 있는지 확인합니다.
• 요소가 세트에 없으면 표시된 스택과 임시 스택에 모두 추가합니다.
• 종료 시간을 기록하고 소요된 총 시간을 계산합니다.
• 결과 반환

예

다음은 HashSet -

public static Stack idea2(Stack stack) {
    long start = System.nanoTime();
    Set seen = new HashSet();
    Stack tempStack = new Stack();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

최적화된 접근 방식을 위해

Set seen

두 가지 접근 방식을 함께 사용

다음은 위에서 언급한 두 가지 접근 방식을 사용하여 특정 스택에서 중복 항목을 제거하는 단계입니다.

• initData(Long size) 메서드를 사용하여 데이터를 초기화하여 임의의 정수로 채워진 스택을 만듭니다.
  
• cloneStack(스택 스택) 메서드를 사용하여 원본 스택의 정확한 복사본을 생성하는 스택을 복제합니다.
• initData를 사용하여 초기 스택을 생성합니다.
• cloneStack을 사용하여 이 스택을 복제합니다.
• 원본 스택에서 중복 항목을 제거하려면  순진한 접근 방식을 적용하세요.
• 복제된 스택에서 중복 항목을 제거하려면 최적화된 접근 방식을 적용하세요.
• 각 방법에 소요된 시간과 두 가지 접근 방식으로 생성된 고유 요소를 표시합니다.

예

다음은 위에 언급된 두 접근 방식을 모두 사용하여 스택에서 중복 요소를 제거하는 Java 프로그램입니다.

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack initData(Long size) {
        Stack stack = new Stack();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i  cloneStack(Stack stack) {
        Stack newStack = new Stack();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack idea1(Stack stack) {
        long start = System.nanoTime();
        Stack resultStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack idea2(Stack stack) {
        long start = System.nanoTime();
        Set seen = new HashSet();
        Stack tempStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack data1 = initData(10L);
        Stack data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: "   idea1(data1));
        System.out.println("Unique elements using idea2: "   idea2(data2));
    }
}

산출

비교

* 측정 단위는 나노초입니다.

public static void main(String[] args) {
    Stack data1 = initData();
    Stack data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}

관찰한 바와 같이, 아이디어 1의 복잡성은 O(n²)인 반면 아이디어 2의 복잡성은 O(n)이기 때문에 아이디어 2의 실행 시간은 아이디어 1보다 짧습니다. 그래서 스택 수가 늘어나면 그에 따라 계산에 소요되는 시간도 늘어납니다.