[SW Expert Academy] 새샘이의 7-3-5 게임 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWZ2IErKCwUDFAUQ

SW Expert Academy

 

HashSet을 ArrayList로 변환

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
 
class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int t = sc.nextInt();
 
        for (int tc = 1; tc <= t; tc++) {
 
            HashSet<Integer> set = new HashSet<>();
            int arr[] = new int[7];
 
            for (int i = 0; i < 7; i++) {
                arr[i] = sc.nextInt();
            }
 
            for (int i = 0; i < 7; i++) {
                for (int j = i + 1; j < 7; j++) {
                    for (int z = j + 1; z < 7; z++) {
                        set.add(arr[i] + arr[j] + arr[z]);
                    }
                }
            }
            // System.out.println(set);
 
            ArrayList<Integer> list = new ArrayList<>(set);
 
            Collections.sort(list);
 
            System.out.print("#" + tc + " " + list.get(list.size() - 5));
             
            System.out.println();
 
        }
 
    }
}

 

TreeSet을 ArrayList로 변환

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {

			TreeSet<Integer> set = new TreeSet<>();
			int arr[] = new int[7];

			for (int i = 0; i < 7; i++) {
				arr[i] = sc.nextInt();
			}

			for (int i = 0; i < 7; i++) {
				for (int j = i + 1; j < 7; j++) {
					for (int z = j + 1; z < 7; z++) {
						set.add(arr[i] + arr[j] + arr[z]);
					}
				}
			}
			// System.out.println(set);

			ArrayList<Integer> list = new ArrayList<>(set);

			//Collections.sort(list);

			System.out.print("#" + tc + " " + list.get(list.size() - 5));
			
			System.out.println();

		}

	}
}

 

HashSet vs TreeSet

1. HashSet:
   • 시간 복잡도: HashSet에 요소를 추가하는 것은 평균적으로 O(1)의 시간이 걸립니다. 모든 조합을 저장한 후 ArrayList로 변환하고 정렬하는 과정이 필요합니다.
   • 공간 복잡도: 필요한 저장 공간은 유일한 합의 개수에 따라 달라지지만, HashSet과 ArrayList 모두 요소의 수에 비례하여 공간을 차지합니다.
   • 특징: 추가 후에 정렬 과정이 필요하여, 이 경우 전체 시간 복잡도에 영향을 줄 수 있습니다. 정렬은 O(N log N)의 시간이 소요됩니다.
2. TreeSet:
   • 시간 복잡도: TreeSet은 내부적으로 균형 이진 검색 트리를 사용하므로 요소를 추가할 때마다 O(log N)의 시간이 걸립니다.
   • 공간 복잡도: TreeSet 역시 요소의 수에 비례하여 공간을 차지합니다.
   • 특징: TreeSet은 요소를 추가하는 즉시 정렬 상태를 유지하므로 별도의 정렬 과정이 필요 없습니다. 이로 인해 마지막에 원하는 순위의 요소를 바로 가져올 수 있습니다.

성능 비교

• HashSet을 사용한 경우: 모든 조합을 먼저 저장한 후에 정렬 과정이 필요합니다. 이는 추가 작업으로 인해 성능 저하가 발생할 수 있습니다.
• TreeSet을 사용한 경우: 요소가 추가될 때 자동으로 정렬되기 때문에 추가적인 정렬 시간이 필요 없습니다. 이는 전체 실행 시간을 줄일 수 있는 장점이 있습니다.

결론

• 만약 순위에 따른 값을 빠르게 추출하는 것이 중요하다면, TreeSet을 사용하는 것이 더 효율적입니다. TreeSet은 추가될 때 자동으로 정렬되므로, 마지막에 리스트를 생성할 때 이미 정렬된 상태를 유지할 수 있습니다.
• 반면, HashSet은 모든 데이터를 처리한 후에 정렬이 필요하므로 처리 시간이 더 오래 걸릴 수 있습니다.