[백준(BOJ)] 10816번 : 숫자 카드 2 - C++[CPP]

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 이분 탐색
• 해시를 사용한 집합과 맵

 

---

⊙ 문제 접근 과정

 

vector를 활용해 값을 입력받고 제일 먼저 해야 할 건 정렬이다.

sort로 정렬을 해주고 algoritm 헤더에 있는 Lower bound와 Upper bound 알고리즘을 사용하면 된다.

참고로 sort도 algoritm 헤더에 있다.

 

그냥 제출하면 시간 초과가 뜬다.

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

 

시간 초과를 해결하기 위해 위 코드를 main함수에 넣어주자.

 

---

⊙ Lower bound

 

선형 구조의 부분 탐색법이다. 이분 탐색과 거의 다를 게 없다.

만약 target 값이 있다면 target 값보다 같거나 큰 첫 번째 위치를 말한다.

 

⊙ Upper bound

 

Lower bound와 차이점 하나만 기억하면 된다.

 

Lower bound는 이상(<=)

Upper bound는 초과(<)

 

target 값보다 큰 첫번째 위치를 말한다.

 

 

예를들어 {1,2,3,3,4}란 배열이 있다.

여기서 target은 3일 때 Lower bound와 Upper bound의 값은 무엇일까?

 

이상(<=), 초과(<)만 기억하고 적용해보자.

 

Lower bound(이상) = 2 (index=위치)

Upper bound(초과) = 4 (index=위치)

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;
vector<int> arr;
vector<int> target;

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    cin >> n;
    int count[n]={0,};
    for(auto i = 0;i<n;i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(),arr.end());

    cin >> m;
    for(auto i =0; i<m;i++) {
        int x;
        cin >> x;

        cout << upper_bound(arr.begin(),arr.end(),x) - lower_bound(arr.begin(),arr.end(),x)<< " ";
    }
}

 

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

아는 만큼 코드 줄을 짧게 가져갈 수 있다.

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!