2.20 hashset vs arrayList

음... 공부할 시간은 없고 프로젝트는 진행하는데
그래도 조금씩 프로젝트가 조금씩 완료가 되는거 같아 다행이다.

내가 백준으로 문제를 풀고 있었는데
https://www.acmicpc.net/problem/3273

요 문제를 풀었다. 처음에 이 문제를 어떻게 접근할수 있을지 고민해봤다.
처음에는 답이 안오다가 빼기를 이용하면 되지 않을까 라는 생각을했다.
그래서 아무생각없이 arrayList로 데이터를 저장하고 2로 나눴기때문에 정렬을 진행해줬다.

처음 코드는

import java.util.*;

public class Main {

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>();

        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();

        // 이 아닐때까지 반복
        while (x != 0) {
            int i = sc.nextInt();
            arr.add(i);
            x--;
        }
        int r = sc.nextInt();

        Collections.sort(arr);
        int answer = 0;

        for (int i = 0; i < arr.size() / 2; i++) {
            int t = r - arr.get(i);

            if(arr.contains(t)) {
                answer++;
            }
        }

        System.out.println(answer);

    }


}

요런식으로 작성했다. /2를 했던이유는 보다 빨리 찾으려고 했던게 가장컷다.
하지만 결과는 시간초과..

음.. 이런건 내가 고민한다고 될거 같지 않아서 
지피티한테 물어봤다.
he say

1. 시간 초과 원인 분석

• arr.contains(t)는 리스트 탐색 연산이고, 시간 복잡도는 O(N) 입니다.
• 이를 반복문 내부에서 사용하면, for 루프의 O(N/2) 와 합쳐져 O(N^2) 가 됩니다.
• 만약 입력값이 크다면, 시간 초과가 발생할 가능성이 높아집니다.

---

2. 해결 방법

리스트 대신 HashSet을 사용하면 탐색 시간을 O(1)로 줄일 수 있음
(리스트에서 contains() 호출 → HashSet에서 contains() 호출로 변경)

라고 했다. 결국 리스트의 컨테인즈는 속도가 느리다는 거였고
hashset으로 계산하면 보다 빠르게 계산할 수 있다 했다.
그리고 코드를 조금 수정하고 제출했더니..
통과..
이로서 arrayList보다 hashset이 빠르다는걸 증명할 수 있었다.