[백준] 10815번 숫자 카드

숫자 카드(https://www.acmicpc.net/problem/10815)

---

1. 이해하기

• 상근이가 가지고 있는 카드 중 특정 카드를 가지고 있는지 찾는 문제이다.
• 이분 탐색문제이다.

---

2. 구현하기

• 단순히 이분탐색을 구현하면 된다.

• binarySearch(key): 중간값이 key에 해당하는지 보면서 검색해나간다.

  bool binarySearch(int n) {
      long long left = 0, right = N-1;
      while(left <= right) {
          long long mid = (left+right)/2;
          if(sang[mid] == n) return true;
          else if(sang[mid] < n) {
              left = mid+1;
          } else {
              right = mid-1;
          }
      }
      return false;
  }

• 이분탐색을 하기 위해서는 배열을 정렬해야한다.

  • 정렬을 하기 위해서는 algorithm의 sort를 사용해도 된다.

  • 그냥 사용하면 재미가 없으므로 퀵소트와 머지소트를 구현한다.

  • 퀵소트

    void findMid(int st, int en) {
        int mid = (st+en)/2;
        int minVal = min(sang[st],min(sang[mid],sang[en]));
        int maxVal = max(sang[st],max(sang[mid],sang[en]));
        if(minVal != sang[mid] and maxVal != sang[mid]) swap(sang[st],sang[mid]);
        else swap(sang[st],sang[en]);
    }
    
    void quickSort(int st, int en) {
        if(st >= en) return;
        findMid(st,en);
        int pivot = sang[st];
        int l = st, r = en;
        while(1) {
            while(l <= r and pivot >= sang[l]) l++;
            while(l <= r and pivot <= sang[r]) r--;
            if(l > r) break;
            swap(sang[l],sang[r]);
        }
        swap(sang[st],sang[r]);
    
        quickSort(st,r-1);
        quickSort(l,en);
    }

    그냥 퀵소트를 구하면 시간초과가 난다. 그 이유는 퀵소트의 최악의 시간은 제곱의 시간이 걸리기 때문이다. 이를 해결하기 위해서 피봇의 값을 단순하게 정하는 것이 아닌 세개의 값을 비교해서 중간값을 피봇값으로 한다. 중간값을 피봇으로 하기 위한 과정이 findMid(st,en)이다.

  • 머지소트

    void mergeSort(int st, int en) {
        if(st >= en) return;
    
        int mid = (st+en)/2;
        mergeSort(st,mid);
        mergeSort(mid+1,en);
    
        int l = st, r = mid+1;
        int tempIdx = st;
        while(l <= mid and r <= en) {
            if(sang[l] < sang[r]) {
                temp[tempIdx++] = sang[l++];
            } else {
                temp[tempIdx++] = sang[r++];
            }
        }
    
        while(l <= mid) temp[tempIdx++] = sang[l++];
        while(r <= en) temp[tempIdx++] = sang[r++];
    
        for(int i = st; i <= en; i++) sang[i] = temp[i];
    }

    머지소트는 최악의 경우에도 로그이므로 그냥 구현해도 된다.

---

3. 전체코드

#include <iostream>
using namespace std;

int sang[500000];
int temp[500000];
int N,M;

bool binarySearch(int n) {
    long long left = 0, right = N-1;
    while(left <= right) {
        long long mid = (left+right)/2;
        if(sang[mid] == n) return true;
        else if(sang[mid] < n) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    return false;
}

void mergeSort(int st, int en) {
    if(st >= en) return;

    int mid = (st+en)/2;
    mergeSort(st,mid);
    mergeSort(mid+1,en);

    int l = st, r = mid+1;
    int tempIdx = st;
    while(l <= mid and r <= en) {
        if(sang[l] < sang[r]) {
            temp[tempIdx++] = sang[l++];
        } else {
            temp[tempIdx++] = sang[r++];
        }
    }

    while(l <= mid) temp[tempIdx++] = sang[l++];
    while(r <= en) temp[tempIdx++] = sang[r++];

    for(int i = st; i <= en; i++) sang[i] = temp[i];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> sang[i];
    mergeSort(0,N-1);
    cin >> M;
    for(int i = 0; i < M; i++) {
        int n;
        cin >> n;
        cout << binarySearch(n) << ' ';
    }
    cout << '\n';
    return 0;
}

여기서 시간초과가 안나게하는 가장 중요한건 정렬이 아니고

ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

이거였다...

너무 많은 값을 받다보니 그런가보다.