[백준]BOJ_10816_숫자 카드 2_S4

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

10816번: 숫자 카드 2

오랜만에 다시 알고리즘 게시물을 작성한다.
그동안 혼자 조용히 풀기도 했고 깃헙에 올리기도 해봤는데, 내가 공부한걸 정리하기에 블로그만한게 없는 것 같다.

일단 누군가에게 설명을 해야하니 더 완벽하게 이해해야하는 것도 있고, 재미도 있어 더 잘 되는 것 같다.
당분간은 많은 문제를 풀기보다 한문제씩 풀면서 이곳에 정리하려한다.
하도 오랫동안 풀지 않아 감이 다 떨어졌기 때문이다.

자, 이제 시작한다.

문제 풀이방법 요약 먼저하고 자세한 설명을 하겠다.
요약을 보고 다시한번 도전해보시는걸 추천드린다.

---

1. 오름차순으로 정렬한다.
2. 찾으려는 수가 처음으로 등장하는 인덱스를 구한다.
3. 찾으려는 수보다 큰 수가 처음으로 등장하는 인덱스를 구한다.
4. 이 두 인덱스는 이분탐색을 이용해 구한다.
5. 구한 두 인덱스의 값의 차가 그 수가 쓰인 개수이다.

---

아래는 예시를 사용한 상세 설명이다.
(https://st-lab.tistory.com/267 이 블로그를 많이 참조했는데, 이 블로그에서 든 예시를 보다 자세히 작성하려한다.)

---

int[] A = {1, 2, 2, 4, 4, 4, 6 ,7, 7, 9};
A라는 배열이 위와 같이 있다고 가정하자.
* 어느 배열이 오건 위와같이 오름차순으로 정렬하는 것이 처음 해야할 작업이다.

A라는 배열에 사용된 4의 개수를 구하려한다.

이때 우리는 직관적으로 3개라는 것을 알 수 있다.
그 생각에는 다음과 같은 과정이 깔려있다.

1. 4가 처음오는 인덱스가 3번이다.
2. 마지막으로 4가 오는 인덱스가 5번이다.
3. 따라서 4가 쓰인 개수는 5 - 3 + 1 해서 3개이다.
* 다른말로 하면 처음 오는 인덱스가 3번이고 4보다 큰 수가 오는 인덱스가 6이니까 6 - 3 해서 3개이구나.

여기서 4가 처음오는 인덱스를 lower_bound 라 하고
4보다 큰 수가오는 첫 인덱스를 upper_bound라 한다.

우리는 lower_bound와 upper_bound를 구한다음 그 차를 구하면 개수를 알 수 있다.
그리고 이 lower_bound와 upper_bound를 구하는 방법으로 이분탐색을 사용한다.

• key = 4 (몇번 사용되었는지 찾으려는 수)
• bottom = key가 처음 등장하는 인덱스
• top = key보다 큰 값이 처음 등장하는 인덱스
• mid = (bottom + key) / 2

시작은 bottom = 0, top = A.length; 으로 시작된다.

---

먼저 upper_bound를 구하는 방법부터 살펴보자.

• A[mid] > key 👉 top = mid
• A[mid] <= key 👉 bottom = mid + 1

중간값인 A[mid]가 key 보다 크면 top을 mid로 줄이고,
A[mid]가 key보다 작거나 같으면 bottom을 mid + 1로 늘리고,
위 과정을 반복하다 bottom이 top과 같아지면 그 값이 upper_bound이다.

• bottom은 0
• top은 10
• mid = (bottom + top) / 2 = 5
• A[mid] = A[5] = 4
• A[mid] = key
• bottom = mid + 1 = 6

이때 bottom = mid + 1로 바꾸어준다.
그냥 mid가 아니라 + 1을 하는 이유는 위에서 마지막으로 4가 오는 인덱스를 구했을 때는 5이고,
처음으로 4보다 큰 수가 오는 인덱스가 6이었던 것 처럼,
우리는 찾으려는 key보다 큰 수가 오는 첫 인덱스인 top을 구하려고 하는 것이기에 mid + 1로 바꾸어준다.
달리 말하면 어차피 A[mid] 의 값이 key와 같은 것을 알기때문에 아직 모르는 A[mid+1]로 바꾸어주는 것이다.

• bottom = 6
• top = 10
• mid = (bottom + top) / 2 = 8
• A[mid] > key
• top = mid = 8

A[mid] > key이므로 top의 값을 낮추어준다.
top을 mid와 같은 값으로 바꾸어주었다.

• bottom = 6
• top = 8
• mid = (bottom + top) / 2 = 7
• A[mid] = A[7] = 7
• A[mid] > key이다.
• top = mid = 7

A[mid] > key이므로 top의 값을 낮추어준다.
top을 mid와 같은 값으로 바꾸어주었다.

• bottom = 6
• top = 7
• mid = (bottom + top) / 2 = 6
• A[mid] = A[6] = 6
• A[mid] > key
• top = mid = 6

이제 bottom = top이 되었으니,
따라서 upper_bound는 6이다.

---

이번에는 lower_bound를 구하는 방법을 살펴보자.

• A[mid] >= key 👉 top = mid
• A[mid] < key 👉 bottom = mid + 1

중간값인 A[mid]가 key 보다 크거나 같으면 top을 mid로 줄이고,
A[mid]가 key보다 작거나 같으면 bottom을 mid + 1로 늘리고,
위 과정을 반복하다 bottom이 top과 같아지면 그 값이 upper_bound이다.

 

여기서 차이점은 upper_bound를 구할때는 A[mid] = key일때 bottom을 mid + 1로 했다는 것이고,
이번에는 lower_bound를 구하는 것이기에 A[mid] = key일때 top을 mid로 줄이는 것이다.

---

• bottom은 0
• top은 10
• mid = (bottom + top) / 2 = 5
• A[mid] = A[5] = 4
• A[mid] = key
• top = mid = 5

---

• bottom = 0
• top = 5
• mid = 2
• A[mid] = A[2] = 2
• A[mid] < key
• bottom = mid + 1 = 3

---

• bottom = 3
• top = 5
• mid = 4
• A[mid] = A[4] = 4
• A[mid] = key
• top = mid = 4

---

• bottom = 3
• top = 4
• mid = 3
• A[mid] = A[3] = 4
• A[mid] = key
• top = mid = 3

---

따라서 lower_bound는 3이다.

결국 key는 4일때 lower_bound는 3이고 uppper_bound는 6이기 때문에
4가 사용된 횟수는 3번이 된다.

---

여기까지 예시였고, 이제 위 과정을 참고해서 코드를 작성해보자.

1. 오름차순으로 정렬한다.
2. 각각의 수가 몇번 사용되었는지 횟수를 구하려는 배열을 반복문을 통해 원소하나씩 가져온다.
3. 해당 원소를 key로 lower_bound와 upper_bound를 구한다.
4. upper_bound - lower_bound를 출력한다.
5. 3번과 4번을 반복한다.

---

 

https://github.com/Headfish96/Online-Judge

GitHub - Headfish96/Online-Judge: This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://gi