BOJ - 숫자카드 2(10816)

풀이1

실버4 : 이분 탐색 문제이다.

생각

특정 숫자가 등장하는 lowerBound와 UpperBound를 잡아내면 끝나는 문제이다.

LowerBound

원하는 숫자가 처음으로 등장하는 곳의 번째

기본적인 이분 탐색은, 내가 탐색한 index를 포함하지 않은 상태로 다음 index를 탐색한다. 그리고 찾으면 return한다. 하지만, 이번에 우리가 할 것은, 해당 숫자의 범위를 탐색하는 것이기 때문에, 찾았다고 해서 탐색을 끝낼 수 없다. 다만, 내가 원하는 값과 같은 값이 있다면, 그 index는 답의 후보가 될 수 있다. 최종적인 답은 끝까지 탐색한 후에 도출되도록 만들어야 한다. 예시를 보자.

0   1   2   3   4   5   6   7   8   9   10
-10 -10 2   3   3   6   7   10  10  10  13

정렬이 된 상태에서 10의 lowerBound를 찾아보자.

#1
start :  0 end : 11 mid :  5 a[5] :  6

이 상황에서 답은 무조건 5보다 큰 index에서 나올 수 밖에 없다. 따라서 start = mid + 1 해준다.

#2
start :  6 end : 11 mid :  8 a[8] : 10

8의 index에서 찾는 값이 나왔다. 해당 index는 답의 후보이다. 그렇기 때문에 이것을 포함한 상태로 다음 값으로 넘어가야 한다. end = mid

#3
start :  6 end :  8 mid :  7 a[7] : 10

또 후보값이 나왔다. 이 때 index가 더 작으면서 10을 만족하기 때문에 end = mid해준다.

#4
start :  6 end :  7 mid :  6 a[6] :  7

7보다 큰곳에서 10은 나온다. 따라서 start = mid + 1 해준다.

#5
start :  7 end :  7 mid :  7 a[7] :  10

start와 end가 같아졌다. 원래 이분탐색과 다르게 이러한 조건 때문에 start = end인 상황에서 탐색을 계속할 수 없다. 같아지는 순간 종료한다.

기본적인 이 알고리즘의 핵심은,

1. 원하는 수를 찾는다.
2. 원하는 수를 찾았으면 그 수를 end에 박아두고 계속 탐색한다.

이렇게 압축할 수 있다. 만약 원하는 수가 없다면 어떻게 될까? 기본적으로 제시한 숫자의 value가 원하는 값보다 크거나 같을 경우, end = mid하기 때문에 없다면 원하는 값보다 큰 수중에서 가장 작은 수의 위치를 return할 것이다. 즉, 1 3 5 7에서 4를 찾는다면, 없기 때문에 lowerBound는 3(index = 2)를 리턴한다.

Code

int lowerBound(int num){
    int start = 0, end = N, mid = 0;
    while (start < end) {
        mid = (start+end)/2;
        if (a[mid] < num) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return end + 1;
}

UpperBound

원하는 숫자보다 처음으로 크게되는 위치

lowerBound와 다르게, 10을 찾는다면, 10보다 처음으로 크게되는 위치를 리턴하게 된다.

이분 탐색으로부터 생각해보자. 원래 같으면 같을 때, 탈출하여 답을 제시한다. 하지만, 내가 원하는 것은 찾은 뒤에 어떠한 조치가 필요하다. 찾은 값은, lowerBound에서와 다르게, 답의 후보가 될 수 없다. 예를 들어, 내가 10이라는 값을 찾았다. 하지만 위에 정한 정의는 10을 찾은 것이 중요한 것이 아니고, 10보다 언제 처음으로 커지냐가 궁금하다. 따라서 찾았다면, 해당 제시한 위치는 답이 될 수 없다. 따라서 이 값을 포함하지 않고 탐색해야 한다. 예시를 보자.

#1
start :  0 end : 11 mid :  5 a[5] :  6

6은 10보다 작으므로 이 곳에서 답이 나올 수는 없다. start = mid + 1

#2
start :  6 end : 11 mid :  8 a[8] : 10

8위치에서 10이 나왔지만, 이 10은 내가 원하는 답이 아니다. start = mid + 1

#3
start :  9 end : 11 mid : 10 a[10] : 13

10의 위치에서 13이 나왔고, 10의 upperBound는 이 값을 포함한 아래 영역에서 나온다. 따라서 해당 10 index는 포함한 상태로 탐색을 진행한다. end = mid

#4
start :  9 end : 10 mid :  9 a[9] : 10

9위치에서 10이 나왔지만, 이 10은 내가 원하는 답이 아니다. start = mid + 1

#5
start :  10 end : 10 mid :  10 a[10] : 13

start = end가 되어 종료한다. upperBound는 10이다.

결국, 어느 범위에서 답이 나타날 수 있는지를 명확하게 규명하는 것이 중요하다. upperBound도 lowerBound와 마찬가지로 탐색하는 값이 없다면 이 값보다 큰 수들 중 가장 작은 수의 위치를 리턴한다. 아, 잘 생각해야 하는 부분이 있는데, 탐색 범위를 0~N-1로 하면 안된다. 그렇게 될 경우, 맨 끝에 내가 찾고싶은 값이 있을 때, 원하는 index를 반환할 수 없다.

1 10 10 10

이런 경우에 10의 upperBound를 찾는다고 해보자. 정의에 의하면 답은 당연히 5이다. 하지만 내가 탐색을 진행할 때, start = 0, end = 3이라고 놓고 생각하면, 최종 탐색 결과는 3을 넘지 못하고 return 값은 1을 더한 4이다. 즉 절대로 4를 넘은 값이 나올 수가 없다. 위에 정의한 upperBound 정의의 일관성을 잃지 않기 위해서는 end의 index를 하나 늘려서 정해놓는 것이 바람직하다.

Code

int upperBound(int num){
    int start = 0, end = N, mid = 0;
    while (start < end) {
        mid = (start+end)/2;
        if (a[mid] <= num) { // 등호만 다르다.
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return end + 1;
}

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
 
using namespace std;
typedef long long ll;
int N, M;
int a[500001];
 
int lowerBound(int num){
    int start = 0, end = N, mid = 0;
    while (start < end) {
        mid = (start+end)/2;
        if (a[mid] < num) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return end + 1;
}
 
int upperBound(int num){
    int start = 0, end = N, mid = 0;
    while (start < end) {
        mid = (start+end)/2;
        if (a[mid] <= num) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return end + 1;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a+N);
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        int num, ans = 0;
        cin >> num;
        int low = lowerBound(num);
        int high = upperBound(num);
        if (low != high) ans = high-low;
        cout << ans << " ";
    }
    return 0;
}
 

STL upperBound, lowerBound를 이용한 풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
 
using namespace std;
typedef long long ll;
int N, M;
int a[500001];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a+N);
 
    cin >> M;
    for (int i = 0; i < M; i++) {
        ll num, ans = 0;
        cin >> num;
        ll low = lower_bound(a, a+N, num)-a;
        ll high = upper_bound(a, a+N, num)-a;
        if (low != high) ans = high-low;
        cout << ans << " ";
    }
    return 0;
}
 

풀이2

실버2 : 정렬 문제이다.

이전에 upper bound, lower bound가 잘 명확히 이해가 안되어서 다시 파이썬으로 풀어보자하고 도전했다.

lower bound

원하는 값보다 큰 값의 시작 index

일단 먼저 알아둬야 하는 것은, lower bound나 upper bound나 오른쪽 index로 답을 내려는 가정이 깔려있다는 사실이다. 그게 가장 중요하다. 그리고 나서 중앙값을 제안했을 때 문제의 목적에 맞게 후보가 되는지만 판단해주면 된다. 두 알고리즘이 공통적으로 가정하는 것을 정리해보자.

1. right index로 답안을 낼 것이다.
2. 나중에 while문을 통과하기 위해 양쪽 index(left, right)를 업데이트 할 때는 left한쪽으로만 이동한다.
   • 즉 이말은 right index는 업데이트 시 mid를 그대로 두고, left만 mid+1로 기존 값을 검사하지 않아 최종적으로 while (left < right) 문을 통과하기 위함이다.

def lower_bound(a, v): # v이하 최대 인덱스
  left = 0
  right = len(a)
  print("left right mid value action")
  while left < right:
    temp = []
    mid = (left+right)//2
    temp.extend(list(map(str, [left, right, mid, v])))
    
    if a[mid] < v:
      left = mid + 1
      temp.append(f'update left to {mid+1}')
    else:
      right = mid
      temp.append(f'update right to {mid}')
    print("     ".join(temp))
  return right

index 0 1 2 3 4 5 6 7 8
list  2 4 5 5 5 7 9 9 9

find 5

위와 같은 문제가 주어졌다고 생각해보자.

left right mid value action
0     9     4     5     update right to 4
0     4     2     5     update right to 2
0     2     1     5     update left to 2
2

자 0과 8을 보고 중간값인 4가 채택된다. 리스트에서 해당되는 값은 5, 원하는 값과 같다. 그런데 우리가 하고싶은게 무엇인가? 이 5가 처음으로 등장하는 곳을 알고 싶은 것이다. 그럼 이녀석은 답이 될 수 있는 후보 이다. 그런데 이 5보다 작은 곳에서 답이 나오면 어떡하지? 그러니까 right 인덱스에 얘를 붙잡아두고 그 사이의 값을 다시 탐색한다. 이 작업의 결과가 두번째 라인이다. 두번쨰에서도 우리는 5를 찾았다. 여전히 새로운 후보이니 붙잡아 둔다. 그런데 그 다음으로 가보니 값이 4가 나왔다. 얘는 후보가 될 수 없다. 그리고 이 4보다 큰쪽에서 5라는 값을 찾아야 하니까 +1하여 left를 업데이트 한다. 이제 right와 left가 값이 2로 같아졌기 때문에 반복문을 탈출하고, 끝난다.

여기서 핵심은, 같은 것이 나왔을 때 어떻게 처리해야 하느냐에의 판단이다. 같은 값이 나오게 되었을 때, lower bound의 경우 왼쪽을 탐색해야 한다.(더 작은 곳에 후보가 있는지) 그렇기 때문에 right를 땡겨오는 것.

upper bound

원하는 값보다 큰 (초과) 첫번째 index

def upper_bound(a, v): # v이하 최대 인덱스
  left = 0
  right = len(a)
  print("left right mid value action")
  while left < right:
    temp = []
    mid = (left+right)//2
    temp.extend(list(map(str, [left, right, mid, v])))
    
    if a[mid] <= v:
      left = mid + 1
      temp.append(f'update left to {mid+1}')
    else:
      right = mid
      temp.append(f'update right to {mid}')
    print("     ".join(temp))
  return right

index 0 1 2 3 4 5 6 7 8
list  2 4 5 5 5 7 9 9 9

find 5

가장 중요한 것은 뭐다? 같았을 때 어디를 탐색해야 하는지이다. 같을 경우, 이번에는 오른쪽을 탐색해야 한다. 왜냐하면 일단 5가 나왔다. 그럼 얘보다 일단 큰 부분에서 답이 나올거아닌가? 그러니 mid+1로 left를 업데이트 한다. 만약에 그 다음 스텝에서 조사한 값이 내가 원하는 값보다 크면, 그럼 답은 더 작은 곳에 있으니 이녀석을 붙잡아 두고(답이 될 수 있는 후보이다.) 다음으로 넘어간다.

left right mid value action
0     9     4     5     update left to 5
5     9     7     5     update right to 7
5     7     6     5     update right to 6
5     6     5     5     update right to 5
5

Code

def lower_bound(a, v): # v이하 최대 인덱스
  left = 0
  right = len(a)
  print("left right mid value action")
  while left < right:
    temp = []
    mid = (left+right)//2
    temp.extend(list(map(str, [left, right, mid, v])))
    
    if a[mid] < v:
      left = mid + 1
      temp.append(f'update left to {mid+1}')
    else:
      right = mid
      temp.append(f'update right to {mid}')
    print("     ".join(temp))
  return right
def upper_bound(a, v): # v이하 최대 인덱스
  left = 0
  right = len(a)
  print("left right mid value action")
  while left < right:
    temp = []
    mid = (left+right)//2
    temp.extend(list(map(str, [left, right, mid, v])))
    
    if a[mid] <= v:
      left = mid + 1
      temp.append(f'update left to {mid+1}')
    else:
      right = mid
      temp.append(f'update right to {mid}')
    print("     ".join(temp))
  return right
a = [2,4,5,5,5,7,9,9,9]
 
lower_bound(a, 5)
upper_bound(a, 5)

Reference

• 백준(10816번) - 숫자카드 2