[BaekJoon] 1920 수 찾기 (java)

🔗 문제 링크

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

👨🏻‍💻 ArrayList로 구현한 코드 (런타임 에러)

import java.util.Scanner;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int nNum = sc.nextInt();
		ArrayList<Integer> nList = new ArrayList<>();
		for(int i = 0; i< nNum; i++) {
			nList.add(sc.nextInt());
		}
		
		int mNum = sc.nextInt();
		int[] mList = new int[mNum];
		for(int i = 0; i< mNum; i++) {
			mList[i] = sc.nextInt();
		}
		
		for(int i = 0; i< mNum; i++) {
			if (nList.contains(mList[i]))
				System.out.println(1);
			else System.out.println(0);
		}
	}

}

👨🏻‍💻 Binary Search로 구현한 코드 (통과)

import java.util.Scanner;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int nNum = sc.nextInt();
		int[] nList = new int[nNum];
		for(int i = 0; i< nNum; i++) {
			nList[i] = sc.nextInt();
		}
		Arrays.sort(nList);
		
		int mNum = sc.nextInt();
		int[] mList = new int[mNum];
		for(int i = 0; i< mNum; i++) {
			mList[i] = sc.nextInt();
		}
		for(int i = 0; i< mNum; i++) {
			System.out.println(binarySearch(nList, mList[i]));
		}
		
	}
	
	public static int binarySearch(int[] nList, int searchNum) {
		int start = 0;
		int end = nList.length-1;
		int cursor = (start+end)/2;
		
		
		while (start <= end) {

			if (nList[cursor] == searchNum) return 1;
			else if (nList[cursor] < searchNum) {
				start = cursor+1;
			}
			else if (nList[cursor] > searchNum) {
				end = cursor-1;
			}
			cursor = (start+end)/2;
		}
		return 0;
	}
}

👨🏻‍💻 HashSet으로 구현한 코드 (통과)

import java.util.Scanner;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		HashSet<Integer> set = new HashSet<>();
		int nNum = sc.nextInt();
		for(int i = 0; i< nNum; i++) {
			set.add(sc.nextInt());
		}
		
		int mNum = sc.nextInt();
		int[] mList = new int[mNum];
		for(int i = 0; i< mNum; i++) {
			mList[i] = sc.nextInt();
		}
		for(int i = 0; i< mNum; i++) {
			if (set.contains(mList[i]))
				System.out.println(1);
			else System.out.println(0);
		}
		
	}
	
}

📝 결론

문제를 풀 때 처음에는 ArrayList를 통해 풀었다. 내가 사용한 ArrayList의 contains메서드는 내부 값들을 전부 탐색을 하게되어 $O(n)$의 시간복잡도를 가지는 ArrayList의 contains메서드를 사용하니 이클립스에서는 잘 돌아가던 코드가 백준에서는 런타임 에러가 발생하였다.

그리하여 시간복잡도를 줄이기 위해 Binary Search를 구현하여 테스트를 해보았더니 결과가 통과되는 것을 확인하였다.

그 외에도 HashSet을 사용하여 문제를 풀어보았다. HashSet 또한 문제는 통과할 수 있었으나 Binary Search와 비교하였을 때 시간이 2배이상 늘어난 것을 확인할 수 있었으며 메모리 사용량 또한 더 많이 사용하는 것을 확인할 수 있었다.

맨 아래에 위치한 테스트는 ArrayList를 사용하여 런타임 에러가 발생한 결괴, 중간 위치한 테스트는 Binary Search를 사용하여 만든 코드의 결과, 맨 위에 위치한 테스트 결과는 HashSet을 사용하여 테스트한 결과이다.