배열 vs ArrayList vs Set 무엇이 더 빠를까?

https://www.acmicpc.net/problem/27622

27622번: Suspicious Event

궁금증은 해당 문제로 해결하였습니다.

문제 지문을 번역해드리자면

 

0이상의 상수 = 로그인

0이하의 상수 = 로그아웃

로그인하지 않고 로그아웃한 이상현상이 발생한 로그의 기록 개수를 출력하시오.

 

배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int n = Integer.parseInt(br.readLine());
		
		boolean[] check = new boolean[1001];
		
		int answer = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(n --> 0) {
			int num = Integer.parseInt(st.nextToken());
			
			if(num < 0) {
				if(check[-num]) {
					check[-num] = false;
				}
				else {
					answer++;
				}
			}
			else {
				check[num] = true;
			}
		}
		System.out.print(answer);
	}
}

1001크기의 boolean 배열을 사용하였습니다.(로그인, 로그아웃만 제공해도 되므로)

ArrayList

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr = new ArrayList<>();
		
		int answer = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(n --> 0) {
			int num = Integer.parseInt(st.nextToken());
			
			if(num < 0) {
				if(arr.contains(-num)) {
					arr.remove(arr.indexOf(-num));
				}
				else {
					answer++;
				}
			}
			else {
				arr.add(num);
			}
		}
		System.out.print(answer);
	}
}

SET

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int n = Integer.parseInt(br.readLine());
		
		HashSet<Integer> set = new HashSet<>();
		
		int answer = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(n --> 0) {
			int num = Integer.parseInt(st.nextToken());
			
			if(num < 0) {
				if(set.contains(-num)) {
					set.remove(-num);
				}
				else {
					answer++;
				}
			}
			else {
				set.add(num);
			}
		}
		System.out.print(answer);
	}
}

 

확실히 크기가 작은 값의 경우 배열이 ArrayList, Set보다는 빠르다는 것을 알 수 있습니다.