백준 10816 - 숫자 카드2 (자바 - 이분탐색)

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

10816번: 숫자 카드 2

 

* 문제 요약

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 갯수 N(1 <= N <= 500,000) 이 주어진다.

둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000 보다 크거나 같고, 10,000,000 보다 작거나 같다.

셋째 줄에는 상근이가 가지고 있는 숫자 카드 중에서 각각 몇개나 존재하는지 구해야할 정수 M개가 주어지며,  이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000 보다 크거나 같고, 10,000,000 보다 작거나 같다.

 

* 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

* 예시

 

* 해결 과정

이 문제는 이분탐색, 또는 해시맵을 활용하여 풀 수 있는 문제이다.

- 첫번째 해결 방법 (이분탐색을 활용한 풀이법)

우선 기본적으로 원활한 이분탐색 활용을 위해 입력받은 데이터들을 오름차순 정렬해주었다.

처음엔 입력받은 데이터 내에 중복된 값이 존재하는지, 중복으로 존재한다면 현재 발견한 숫자가 몇번째 숫자인지 알 수 없으므로 현재 발견한 숫자의 왼쪽, 오른쪽 두 방향으로 순차탐색을 하며 현재 발견한 숫자가 몇 개인지 확인하는 방식으로 코드를 작성하였는데, 63퍼센트에서 시간초과 라는 결과를 받았다.

 

혹시 반복문 2개를 활용해서 각각 다른 방향으로 탐색을 수행시키는게 문제인가 싶어 이분탐색에서 중복된 값이 존재하는 경우 그 값들 중 가장 앞에있는 값의 인덱스를 찾는 법을 알아낸 다음, 중복된 값들 중에서 어떤 숫자가 최초로 발견될 경우 다른 숫자가 나올 때까지 오른쪽 방향으로만 순차탐색을 하여 해당 숫자가 몇 개인지 구했으나, 이 방법도 63퍼센트에서 시간초과라는 결과를 받았다.

 

결국 이분탐색을 할 때 중복된 숫자가 존재할 경우 해당 숫자의 가장 앞에있는 값의 인덱스와 가장 마지막에 있는 인덱스를 찾은 다음, 두 인덱스간의 차이 + 1 을 해주는 식으로 해당 숫자의 갯수를 구해서 문제를 풀었다.

(만약 찾고자 하는 값이 존재하지 않는 경우 두 인덱스간의 차이 + 1 을 해주면 0 이라는 결과를 얻게 된다.)

- lowerBound(int findNumber) : 중복된 값들 중 가장 앞에있는 값의 인덱스를 찾는 메소드

- upperBound(int findNumber) : 중복된 값들 중 가장 마지막에 있는 값의 인덱스를 찾는 메소드

참고 - 이분탐색에서 중복이 발생할 경우 중복 원소 중 첫번째 인덱스와 마지막 인덱스 구하기 : https://devfunny.tistory.com/674

binarySearch 이진탐색의 lowerBound, upperBound (중복 원소 중 첫번째 인덱스와 마지막 인덱스 구하기)

 

* 코드(이분탐색)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().solution();
	}

	static int[] numberArray = null;

	private void solution() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		numberArray = new int[n];
		String[] input = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			numberArray[i] = Integer.parseInt(input[i]);
		}

		Arrays.sort(numberArray);

		int m = Integer.parseInt(br.readLine());
		input = br.readLine().split(" ");
		for (int i = 0; i < m; i++) {
			int findNumber = Integer.parseInt(input[i]);

			int start = lowerBound(findNumber);
			int end = upperBound(findNumber);

			bw.write((end - start + 1) + " ");

		}

		bw.flush();
		bw.close();
		br.close();
	}

	private int lowerBound(int findNumber) {
		int start = 0;
		int end = numberArray.length;

		while (start < end) {
			int mid = (start + end) / 2;
			if (numberArray[mid] >= findNumber) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return start;
	}

	private int upperBound(int findNumber) {
		int start = 0;
		int end = numberArray.length;

		while (start < end) {
			int mid = (start + end) / 2;

			if (numberArray[mid] <= findNumber) {
				start = mid + 1;
			} else {
				end = mid;
			}
		}
		return start - 1;
	}
}

 

- 두번째 해결 방법(해시맵과 Chaining을 활용한 풀이법)

해시맵을 활용할 경우 코드를 좀 더 간결하게 하여 문제를 풀 수 있었다.

우선 Integer 를 key 값, LinkedList<Integer> 객체를 value 값으로 하는 해시맵을 만들어주고 이 해시맵에 입력된 값을 key 로 하고 해당 숫자가 입력될 때마다 LinkedList 에 값을 하나씩 추가해서 결과적으로 LinkedList 의 크기가 key 값이 입력된 횟수가 되게끔 만들어주었다.

 

이후 찾고자 하는 숫자들 하나하나에 대해 특정 숫자가 해시맵에 key 값으로 존재하는 경우 key 값에 할당된 메모리 주소에 저장되어 있는 LinkedList 를 불러와서 리스트의 크기를 출력시켜 주고, 만약 해시맵에 특정 숫자가 key 값으로 존재하지 않는 경우 0을 출력시켜 주었다.

 

* 코드(해시맵)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		HashMap<Integer, LinkedList<Integer>> hashmap = new HashMap<Integer, LinkedList<Integer>>();
		
		int cardCount = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < cardCount; i++) {
			int number = Integer.parseInt(st.nextToken());
			LinkedList<Integer> list = new LinkedList<Integer>();
			if(hashmap.containsKey(number)) {
				list = hashmap.get(number);
				list.add(0);
				hashmap.replace(number, list);
			}
			else {
				list.add(0);
				hashmap.put(number, list);
			}
		}
		
		int possession = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < possession; i++) {
			int number = Integer.parseInt(st.nextToken());
			LinkedList<Integer> list = new LinkedList<Integer>();
			if(hashmap.containsKey(number)) {
				list = hashmap.get(number);
				bw.write(list.size() + " ");
			}
			else
				bw.write(0 + " ");
		}
		
		bw.flush();
		bw.close();
	}
}

 

이분탐색으로 풀었을 경우 메모리는 150,216KB, 처리시간은 1584ms 만큼 걸렸고, 해시맵으로 풀었을 경우 메모리는 197,396KB, 처리시간은 1244ms 만큼 걸렸다.

이렇게 두 풀이방식이 사용한 메모리와 처리시간이 달라진 이유는 이분탐색을 활용할 때와 해시맵을 활용할 때 시간복잡도와 공간복잡도가 완전히 달라지기 때문이다.

 

* 해시맵의 경우

참조 : https://esoongan.tistory.com/193

[Java] 자바의 HashMap에 대해 알아보자

우선 해시맵의 경우 이분탐색 방식으로 풀었을 때보다 메모리를 더 많이 사용했으나 처리시간이 더 빠른것을 알 수 있다.

여기서 해시맵은 내부에 데이터를 저장하기 위한 해시 버킷을 가지고 있는데, 이 버킷의 기본값은 16이며, 데이터가 일정한 갯수 이상이 되면 2배씩 증가시키면서 최종적으로 최대 2^30 개 까지 해시 버킷의 갯수를 증가시킨다.

그런데 이 문제의 경우 입력 갯수가 최대 500,000 개가 될 수 있기 때문에 그만큼 자연스럽게 해시맵이 내부적으로 가지고 있는 해시 버킷의 갯수가 많아지게 되는 점이 첫번째로 메모리 사용량이 많아진 원인이 되었다.

 

두번째로는 해시맵 내부에서 일어나는 충돌 문제를 방지하기 위해 Chaining 기법을 활용했기 때문이다.

여기서 충돌이란 해시맵에서 데이터를 저장할 때 해당 데이터의 key 값을 매개변수로 해시 함수를 실행시켜 얻은 값을 메모리 주소로 할당하여 해당 메모리 주소에 데이터를 저장하게 되는데, 이때 해시맵에 저장되는 데이터가 많아지게 되면 서로 다른 key 값을 매개변수로 하여 해시 함수를 실행했음에도 불구하고 서로 같은 메모리 주소를 할당받게 되는 경우가 존재한다. 이렇게 key 값이 서로 다름에도 불구하고 같은 메모리 주소를 할당받게 되는 경우를 충돌(Collision) 이라고 한다.

 

이 충돌 문제를 해결하기 위해 Chaining 기법을 활용할 수 있는데, 충돌이 발생해 서로 같은 주소를 할당받게 되는 경우 해당 주소의 데이터를 LinkedList 형태로 저장시켜서 서로 다른 데이터들을 리스트에 연속적으로 저장하는 것을 Chaining 기법이라고 한다.

이 문제의 경우 상근이가 가지고 있는 숫자 카드에 적혀있는 숫자를  key 값으로 해시맵에 저장하면, 해당 숫자가 중복으로 존재하는 경우 해시맵에서 해당 숫자를 key 값으로 하여 해시 함수를 실행했을 때 결국 메모리 주소 충돌을 피할 수 없게 된다.(서로 다른 key 값 끼리도 해시 함수 실행결과로 얻은 값이 서로 충돌할 수 있는데, 같은 값으로 해시 함수를 실행하는 경우는 두 말할 것도 없다.)

 

결국 우리는 특정 숫자가 적혀있는 숫자 카드의 갯수를 구해야 하기 때문에 해시맵 내부에서 할당받은 메모리 주소간 충돌이 발생할 경우, 해당 메모리 주소에 있는 값이 덮어씌워지는게 아니라 같은 메모리 주소를 할당받아서 충돌이 발생한 횟수를 알아내야 한다.

(자바의 경우 이미 존재하는 key 값이 저장될 경우 해당 메모리 주소의 데이터가 새로 입력되는 데이터로 덮어씌워진다.)

그렇기 때문에 충돌을 방지하기 위한 Chaining 기법을 응용 했는데, 이 과정에서 만들어진 LinkedList 가 길어지면 길어질수록. 즉, 충돌이 많으면 많아질수록 자연스럽게 사용하게 되는 메모리의 양이 많아질 수 밖에 없게 되는 것이다.

 

반면에 해시맵을 활용할 경우 이분탐색을 활용했을 때보다 처리시간이 짧은 것을 알 수 있는데, 이는 기본적으로 해시맵에서 특정 key 값이 존재하는지 확인할 때 배열에서 인덱스를 기반으로 특정 데이터를 탐색하는 것 처럼 key 값이 하나의 인덱스로 활용되어 해시맵 내부를 탐색하는데, 이때 배열에서의 데이터 탐색과 똑같이 시간복잡도가 O(1) 정도밖에 되지 않기 때문이다.

 

 

* 이분탐색의 경우

해시맵은 위에서 이미 설명했지만 데이터의 양이 많으면 많아질수록 해시 버킷의 갯수가 많아지는것, 그리고 충돌을 방지하기 위해 Chaining 기법을 활용하는데, 이때 충돌이 많으면 많아질수록 LinkedList 의 크기가 커지므로 입력 데이터가 많아지면 자연스럽게 사용되는 메모리의 양 또한 많아질수 밖에 없는데,

이분탐색의 경우 입력받은 데이터를 배열에 저장시켜 주기만 해도 다른 자료구조가 필요하지 않기 때문에 당연히 해시맵보다 메모리의 사용량이 작을 수 밖에 없다.

 

그러나 처리시간의 경우 특정 데이터가 존재하는 경우 O(1) 의 시간복잡도 만으로 해당 데이터를 찾을 수 있는 해시맵과는 다르게 이분탐색이라는 알고리즘을 이용해서 특정 로직을 거쳐 찾고자 하는 숫자가 존재하는지, 존재한다면 해당 숫자가 시작되는 부분과 끝나는 부분의 범위가 어떻게 되는지 알아내는 과정이 필요하므로 해시맵에 비해 데이터를 탐색하는 과정이 복잡하다. 그렇기 때문에 해시맵에 비해 처리시간이 좀 더 오래걸릴 수 밖에 없다.

 

순수 이분탐색의 경우 시간복잡도가 O(logN) 인데, 이 문제에서는 중복된 숫자가 존재하는것 때문에 특정 숫자가 최초로 시작되는 곳, 마지막으로 끝나는 곳, 총 두 가지 위치를 찾아야 했기 때문에 이분탐색을 두번이나 수행했다. 즉, 이 문제를 이분탐색으로 풀었을 경우 각 숫자에 대한 탐색에 걸리는 시간복잡도가 적어도 O(2logN) 정도는 되는 것이다.

(해시맵의 경우 각 숫자에 대한 탐색에 걸리는 시간복잡도가 O(1) 이다.)

 

이러한 이유들 때문에 해시맵을 활용한 경우 이분탐색을 활용했을 때 보다 메모리 사용량이 많으나 처리속도가 빠르고, 이분탐색을 활용한 경우 해시맵을 활용했을 때 보다 처리속도가 느리나 메모리 사용량이 작아지게 된다.