[Binary Search] 백준 - 10816

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

10816번: 숫자 카드 2

 

숫자 카드에 대한 풀이 이다.

이 문제는 기존의 이분탐색 문제와 조금 다른 부분이 있다.

기존에는 값의 범위나, 배열의 범위를 통해서 단일의 값이나 정답을 구하는 문제였지만,

이 문제의 경우에는 한 배열에서 해당과 같은 값의 수를 구하는 것이다.

 

배열의 탐색, 정렬에 대한 특성 중 하나를 기억 해두자

그것은 바로, 정렬된 배열에서는 자신의 값과 유사하거나 같은 값들이 인접한 인덱스에 존재한다는 것이다.

이를 바탕으로 진행해본다면 아래와 같은 메커니즘으로 문제를 풀수있다.

 

1. 배열을 정렬한다.

2. 이분탐색으로 해당과 같은 값을 mid값과 일치할때까지 이분탐색을 한다.

3. 값을 찾으면 해당 값의 +1, -1에 해당하는 값을 right index, left index로 두고 mid값과 같지않을때까지 ++ 혹은 --를 시켜준다.

 

아래는 소스로 구현한 것이다.

 

우선 메인은 간단하게 꾸민다. 찾고자하는 대상의 배열을 하나씩 넘겨줘서처리 한다.

 

 

해당과 같은 방법으로, left_index, right_index를 구해서 ++ 혹은 --를 해서 최대의 각 인덱스를구한다.

이는 값을 찾을때, flag boolean변수를 바꿔주면서 계산에 용이하게 해준다.