[알고리즘] 숫자 카드 2 (백준 10816번)

 

10816번: 숫자 카드 2

 이분탐색이라 쉬울 줄 알았는데 중복된 수를 허용하기 때문에 처음 만나보는 유형이었다.

 사실 HashMap으로 풀면 그만이지만 너무 쉬운거 보단 그래도 이분탐색으로 풀어보고 싶어서 해봤는데 계속 시간 초과가 나서 결국 질문을 보아하니 lowerBound와 upperBound를 사용해야 한다고 한다.

 

 

Solution 1) HashMap 사용

 그냥 입력 받는 값들을 key값으로 HashMap에 저장하고 value는 해당 key의 개수를 넣으면 된다. 굳이 lowerBound, upperBound를 사용하는 것보다 훨씬 쉽고 정석적이지만 메모리 사용량은 더 많이 든다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		StringTokenizer strtok = new StringTokenizer(br.readLine());

		HashMap<Integer, Integer> map = new HashMap<>();
		
		for(int i = 0;i < N;i++)
		{
			int num = Integer.parseInt(strtok.nextToken());
			map.putIfAbsent(num, 0);
			map.replace(num, map.get(num) + 1);
		}

		int M = Integer.parseInt(br.readLine());

		strtok = new StringTokenizer(br.readLine());

		for(int i = 0;i < M;i++)
		{
			int key = Integer.parseInt(strtok.nextToken());

			if(!map.containsKey(key))
				bw.write("0 ");
			else
				bw.write(map.get(key)+" ");
		}

		bw.close();
	}



	public static void main(String[] args) {
		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}

 

---

Solution 2) lowerBound, upperBound 사용

 말 그대로 해당 수의 하한선, 상한선을 구하는 것이다. 이것 또한 binarySearch를 이용하지만 일반적인 binarySearch랑은 조금 다르다.

 

BinarySearch

	static int binarySearch(int list[], int key)
	{
		int left = 0;
		int right = list.length - 1;

		while(left <= right)
		{
			int mid = (left + right) / 2;

			if(list[mid] == key)
				return mid;
			else if(list[mid] < key)
				left = mid + 1;
			else
				right = mid - 1;
		}

		return -1;
	}

 이것이 일반적으로 우리가 사용하는 이분탐색 메서드이다. key 값을 찾으면 바로 index를 return 하고 못 찾으면 -1을 return 한다.

 

lowerBound, upperBound

	static int lowerBound(int list[], int key)
	{
		int left = 0;
		int right = list.length;

		while(left < right)
		{
			int mid = (left + right) / 2;

			if(list[mid] >= key)
				right = mid;
			else
				left = mid + 1;
		}

		return left;
	}

	static int upperBound(int list[], int key)
	{
		int left = 0;
		int right = list.length;

		while(left < right)
		{
			int mid = (left + right) / 2;

			if(list[mid] <= key)
				left = mid + 1;
			else
				right = mid;
		}

		return left;
	}

 하지만 lowerBound, upperBound는 key값을 찾아도 끝나지 않고 계속 탐색 범위를 줄여가며 탐색을 한다. lowerBound는 왼쪽, upperBound는 오른쪽으로 줄여간다.

 

 개념 자체는 어렵지 않지만 구현 시 유의해야할 차이점들이 있다.

1. 탐색 범위를 0 ~ list.length - 1 이 아닌 0 ~ list.length 까지로 설정하게 된다.
2. while문의 조건문이 left <= right 가 아닌 left < right 이다.
3. 왼쪽 절반으로 탐색 범위를 줄일 때 right = mid 이다.
4. left값을 반환한다.

이걸 지키지 않으면 어떤 특정 테스트 케이스에서 틀리게 된다.