[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

 

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

10816번: 숫자 카드 2

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

직전 문제랑 비슷하지만, 이분 탐색을 활용해야 할 경우 조금 고려해야 할 부분이 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제 자체는 그리 어렵지 않다. 사실 이분 탐색을 쓰지 않고도 카운팅 정렬 형식을 사용하여 풀 수도 있다만, 그래도 이분 탐색 카테고리에 있는 만큼 한 번 이분 탐색 풀이 방식을 통해 풀이를 해보도록 하자.

 

 

 

일단, 이분 탐색의 경우 구간의 중간 위치의 값과 key(찾고자 하는 값)를 비교하여 구간을 절반으로 줄여나가며 풀이하는 것이다.

이에 대한 기본적인 과정은 다음 글을 읽어보는 것을 추천한다.

 

https://st-lab.tistory.com/261

[백준] 1920번 : 수 찾기 - JAVA [자바]

 

 

그러다가 array[mid] 값과 key값이 동일하면 반환을 했었다.

 

 

하지만, 이 번 문제의 경우 우리가 고려해야 할 점은 '중복 원소의 개수'를 알아내는 것이다.

직전의 문제인 수 찾기의 경우 찾고자 하는 원소가 있는지를 알아내기만 하면 되기 때문에 구현의 어려움은 없었지만, 이 번 문제의 경우 같은 원소가 있을 때의 값을 알아내야 하기 때문에 몇 가지를 고려하여 작성되어야 한다.

 

 

그럼 어떻게 풀이해야 할까?

 

바로 중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 각각 알아내는 것이다.

무슨 말인가 하면 이렇다.

 

위 배열에서 4라는 값을 찾을 때 4라는 값이 위치하는 가장 왼쪽의 인덱스와 가장 오른쪽의 인덱스를 얻어내어 구간의 길이를 얻어낼 수 없을까? 라는 접근 방식인 것이다.

 

 

 

이 방식으로 접근하기 위해서 먼저 우리는 lower_bound 와 upper_bound 를 알아야 한다.

아마 C++ 에서는 많이 본 적이 있을텐데 아쉽게도 자바에서는 각각의 함수를 따로 제공하고 있지 않고 binarySearch() 메소드를 통한 lower_bound 형식의 이분 탐색만을 제공하고 있다.

 

 

그러면 lower bound와 upper bound의 차이가 무엇인지 알아보자.

일단, 번역을 하자면 lower bound 는 '하한'을 의미하며, upper bound는 '상한'을 의미한다. 흔히 경계를 의미하는 뜻에서 하계, 상계라고도 한다.

 

우리가 하한선, 상한선이라고 할 때 그 하한, 상한을 의미한다.

 

 

그럼 lower bound 부터 보자.

lower bound, 즉 하한은 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미한다.

 

여기서 중요한 점은 '이상'의 값이다. 즉, 왼쪽부터 볼 떄 찾고자하는 값이 같거나 큰 경우를 처음 만나는 위치를 의미한다. 그림으로 보자면 다음과 같다.

 

 

 

위 이미지에서 처음으로 마주하는 key값 이상을 갖고있는 index는 3이다.

즉, lower bound의 값은 3이 된다.

 

 

 

그럼 upper bound 는 무엇일까?

upper bound, 즉 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다. 이 말은 반대로 찾고자 하는 값이 더이상 넘어 갈 수 없는 위치를 의미하기도 하기에 상한(상계)라고 한다.

 

위 이미지에서 그럼 key값인 4를 초과한 처음 만나는 인덱스는 어디일까? 바로 index 6이다.

좀 더 이해를 돕기 위해 이미지로 보자면 다음과 같다.

 

 

 

무슨 말인지 조금은 이해가 가는가? 쉽게 말해 찾고자 하는 값보다 큰 값의 위치를 반환하는 것이 바로 upper bound다.

 

 

 

 

그러면 조금만 더 생각을 해보자.

위 배열에서 보면 5라는 값은 갖고있지 않다. 그러면 key=5 일 때 lower bound와 upper bound의 위치는 각각 어디일까?

 

위 방식 그대로 5 이상의 값을 가진 인덱스와, 5 초과의 값을 가진 인덱스를 찾아내면 된다.

 

 

 위 이미지 처럼 key 값인 5가 처음으로 같거나 큰 값이 index 6의 6임과 동시에 초과한 값도 6이다.

 

즉, 같은 위치를 가리키게 되는 것이다.

 

 

 

이렇게 lower_bound와 upper_bound에 대해 알아보았다.

 

여러분도 이쯤이면 눈치를 채셨겠지만, 위 두 방식을 통해 구간의 길이를 알아낼 수 있게 된다.

중복 원소에 대한 길이 =  (상한 - 하한) 

 

만약 원소가 존재하지 않는다면 상한과 하한 모두 같은 인덱스를 가리키고 있을 것이기에 0이 되므로 이 또한 존재하지 않는 원소를 찾으려 할 경우의 예외 또한 안전하다.

 

 

 

 

 

그러면 이제 각각의 구현 방식에 대한 문제만 남았다.

 

많은 분들이 이분 탐색 과정에서 조건식을 어떻게 구현해야 하는가에 대해 헷갈려 하는데, 이분 탐색의 원리를 이해하기만 한다면 사실 그리 어렵지는 않다.

 

이분 탐색의 원리는 구간 내의 중앙 위치의 값을 기준으로 key 값과 비교를 한 뒤, 상한선(hi)을 내릴 것인지, 하한선(lo)을 올릴 것인지를 결정하는 것이다.

 

그러면 생각해보자. 중앙 위치의 값이 앞뒤로도 연속 된 같은 값을 갖고 있다고 할 때, key값과 중앙 위치의 값이 같게 되었다. 이 때, 만약 하한 값을 찾기 위해서는 상한선을 내려야 할까, 하한선을 올려야 할까?

하한 값을 찾는 다는 것은 같은 값이 있는 요소들의 가장 왼쪽을 찾아내야한다는 것이다. 즉, 왼쪽으로 범위를 좁혀야하지 않겠는가? 그러므로 탐색 구간의 상한선을 내려야한다.

 

반대로 상한 값을 찾기위해서는? 하한과 반대로 오른쪽으로 범위를 좁혀나가야 하기 때문에 당연히 탐색 구간의 하한선을 올려야한다.

 

글로만 보면 이해가 어려울테니 한 번 아래 두 가지 케이스를 보자.

 

 

[Lower bound]

 

 

 

[Upper bound]

 

 

 

 

 

그럼 위를 토대로 Lower Bound와 Upper Bound를 작성해보면 다음과 같다.

 

private static int lowerBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 

	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {

		int mid = (lo + hi) / 2; // 중간위치를 구한다.

		/*
		 *  key 값이 중간 위치의 값보다 작거나 같을 경우
		 *  
		 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
		 */
		if (key <= arr[mid]) {
			hi = mid;
		}

		else {
			lo = mid + 1;
		}

	}
	return lo;
}

private static int upperBound(int[] arr, int key) {
	int lo = 0; 
	int hi = arr.length; 

	// lo가 hi랑 같아질 때 까지 반복
	while (lo < hi) {

		int mid = (lo + hi) / 2; // 중간위치를 구한다.

		// key값이 중간 위치의 값보다 작을 경우
		if (key < arr[mid]) {
			hi = mid;
		}
		// 중복원소의 경우 else에서 처리된다.
		else {
			lo = mid + 1;
		}
	}
	return lo;
}

 

 

 

이를 토대로 하나의 key값에 대해 lower bound를 통해 얻어진 값과 upper bound를 통해 얻어진 값의 차를 구하면 된다.

 

 

※그리고 중요한 점이 있다.

현재 문제에서는 중간 값을 구할 때 mid = (lo + hi) / 2 를 해도 문제가 없지만, 사실 값의 범위가 클 경우에는 int overflow가 발생할 수 있다.

 

쉽게 가정해서 lo = 1, hi = 2147483647 (= Integer.MAX_VALUE) 이렇다면,

(lo + hi) 과정에서 overflow가 발생하여 -2147483648 가 되고, 여기에 2를 나누게 되어 -1073741824 라는 잘못된 값을 반환할 수 있다.

 

이러한 경우 어떻게 해결하냐면, 결국 lo와 hi의 중간 값이라는 것은 lo 로부터 hi까지의 거리를 2로 나눈 값을 더한 값이라는 것이다.

 

무슨 말인가 하면, 

lo = 3, hi = 7 이라 할 때, 중간 값은 (3 + 7) / 2 = 5 일 것이다.

 

이렇게 위와 같이 표현 할 수 있지만, 사실 생각해보면, 3 ~ 7까지 거리라는 건  결국 3을 기준으로 7이 얼만큼 떨어져 있는가이다.

즉, 3으로부터 4만큼 떨어져있는 지점은 7이라는 것이고, 만약 두 지점의 중간 값이라면, 떨어진 거리의 절반이라는 것이다.

 

그러면 다음과 같이 표현 할 수 있다.

중간 지점 = 시작점 + (거리 차) / 2

 

이를 수식으로 표현하면 다음과 같다.

mid = lo + ((hi - lo) / 2)

 

즉, overflow를 생각한다면, 위와 같이 중간 값을 구해줄 수 있다.

 

 

 

그 외의 다른 풀이 방법으로는 HashMap을 사용하는 방법도 있고, Counting 정렬처럼 원소의 값을 배열의 인덱스로 써서 활용하는 방법도 있다.

 

이 부분에 대해서는 별다른 언급 없이 풀이 방법으로 보여주도록 하겠다.

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

이 문제의 경우 풀이 방법은 워낙 다양하지만, 일단 이분 탐색을 기준으로 입력의 차이를 두어 Scanner와 BufferedReader을 각각 사용하여 풀어보고, 나머지 두 방식은 HashMap과 counting 방식을 활용하여 풀어보도록 하겠다.

 

 

1. Scanner + 이분 탐색

2. BufferedReader + 이분 탐색

3. HashMap

4. Counting

 

 

 

---

• 풀이

- 방법 1 : [Scanner + 이분 탐색]

 

import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		Arrays.sort(arr);	// 이분 탐색을 하기 위해서는 반드시 정렬되어있어야 한다.
		
		int M = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			int key = in.nextInt();

			// upperBound와 lowerBound의 차이 값을 구한다.
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		System.out.println(sb);
	}


	private static int lowerBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 

		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {

			int mid = (lo + hi) / 2; // 중간위치를 구한다.

			/*
			 *  key 값이 중간 위치의 값보다 작거나 같을 경우
			 *  
			 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
			 */
			if (key <= arr[mid]) {
				hi = mid;
			}

			else {
				lo = mid + 1;
			}

		}

		return lo;
	}

	private static int upperBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 

		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {

			int mid = (lo + hi) / 2; // 중간위치를 구한다.

			// key값이 중간 위치의 값보다 작을 경우
			if (key < arr[mid]) {
				hi = mid;
			}
			// 중복원소의 경우 else에서 처리된다.
			else {
				lo = mid + 1;
			}

		}

		return lo;
	}
	
}

 

 

 

위에서 작성한 메소드를 그대로 갖고온 것이라 그리 어렵지는 않을 것이다.

 

 

 

 

---

- 방법 2 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

 

 

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

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());
		int[] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine()," ");
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			int key = Integer.parseInt(st.nextToken());

			// upperBound와 lowerBound의 차이 값을 구한다.
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		System.out.println(sb);
	}

	private static int lowerBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 

		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {

			int mid = (lo + hi) / 2; // 중간위치를 구한다.

			/*
			 *  key 값이 중간 위치의 값보다 작거나 같을 경우
			 *  
			 *  (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
			 */
			if (key <= arr[mid]) {
				hi = mid;
			}

			else {
				lo = mid + 1;
			}

		}

		return lo;
	}

	private static int upperBound(int[] arr, int key) {
		int lo = 0; 
		int hi = arr.length; 

		// lo가 hi랑 같아질 때 까지 반복
		while (lo < hi) {

			int mid = (lo + hi) / 2; // 중간위치를 구한다.

			// key값이 중간 위치의 값보다 작을 경우
			if (key < arr[mid]) {
				hi = mid;
			}
			// 중복원소의 경우 else에서 처리된다.
			else {
				lo = mid + 1;
			}

		}

		return lo;
	}
	
	
}

 

 

 

 

 

 

---

- 방법 3 : [HashMap]

 

 

 

 

이분 탐색이 아닌 HashMap 자료구조를 활용 한 방식이다. 이 방식이 이분 탐색보다는 확실하게 빠르지만, 만약 자료구조까지 구현을 해야하는 상황일 경우에는 코드를 작성하는데 시간이 상당히 걸릴 수도 있으니 유의해야한다.

 

 

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

import java.util.StringTokenizer;
import java.util.HashMap;


public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/*
		 *  HashMap<Key, Value>
		 *  Key = 입력되는 원소
		 *  Value = 원소의 개수(=중복 입력 된 원소의 수) 
		 */
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			int key = Integer.parseInt(st.nextToken());
			
			/* 
			 * getOrDefault(key, defaultValue)
			 * key에 대해 map에 저장 된 value를 반환한다.
			 * 만약 value가 없을 경우 defaultValue값을 반환한다.
			 */
			map.put(key, map.getOrDefault(key, 0) + 1);
		}
		
		int M = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < M; i++) {
			int key = Integer.parseInt(st.nextToken());
			
			sb.append(map.getOrDefault(key, 0)).append(' ');
		}
		
		System.out.println(sb);
	}
}

 

 

 

 

---

- 방법 4 : [Counting]

 

 

 

 

또 다른 방법인 원소를 인덱스로 삼아서 숫자의 개수를 카운팅 하는 방식이다. 가장 빠르긴 하나 대신에 수의 범위가 커질 경우(특히 자바에서는 배열의 최대 길이가 int 범위를 넘지 못하며 메모리 낭비가 심하다.)에는 사용하기 힘든 방법이다.

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int[] counting = new int[20000001]; // 입력받는 수의 범위 : -10,000,000 ~ 10,000,000
		
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0 ; i < N; i++) {
			counting[Integer.parseInt(st.nextToken()) + 10000000]++;	// 해당 인덱스의 값 증가
		}
		
		int M = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			sb.append(counting[Integer.parseInt(st.nextToken()) + 10000000]).append(' ');
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

 

채점 번호 : 31907930  -  방법 4 : Counting

채점 번호 : 31907916  -  방법 3 : HashMap

 

채점 번호 : 31907908  -  방법 2 : BufferedReader + 이분 탐색

채점 번호 : 31907896  -  방법 1 : Scanner + 이분 탐색

 

 

보다시피 카운팅 방식이 가장 빠른 방식이다.

Counting과 HashMap 모두 O(N)의 시간복잡도를 갖고있지만, HashMap의 경우 hashing, resizing, comparing 등의 여러 복잡한 과정을 거치기 때문에 조금 더 시간이 걸리는 건 사실이나, 그래도 빠른 방식인 것은 맞다.

 

반대로 이분탐색의 경우 O(NlogN)의 시간복잡도를 갖고있어 상대적으로 O(N) 알고리즘에 비해 느리나 구현이 간편하면서 느린 알고리즘은 아니기 때문에 매우 유용한 알고리즘이기도 하다.

 

 

---

• 정리

 

오늘 이분 탐색 중 중복 원소에 대한 처리 방식에 대해 lower bound와 upper bound을 알아보았다. 이 방법이 나중에 정렬되어있는 원소들 중 특정 위치를 찾아나가거나, 특정 값 이상, 초과, 이하, 미만 등의 여러분이 필요로 하는 값들의 집합을 구할 때도 매우 유용하며 이를 응용해서 Binary Search를 이용한 Insertion Sort(삽입 정렬)에서 안장정렬을 유지할 수 있게 해주기도 한다.

 

C++에서는 위 두 함수를 지원해주고 있지만, 적어도 원리는 알고있는 편이 좋을 것 같아 조금 글이 길어지더라도 설명을 해보았다.

 

 

여담으로 근래 워낙 바빠서 포스팅 업로딩이 조금 늦고 있다.. (죄송합니다..) 그렇다고 블로그에 소홀해진 것은 아니니 걱정하지 않아주셨으면 하고, 그럼에도 많은 분들이 방문해주셔서 감사할 따름이다.

 

만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.