[BOJ/C++] 10807. 개수 세기

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

10807번: 개수 세기

 

개수 세기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

8339

6033

5281

73.531%

문제

총 N개의 정수가 주어졌을 때, 정수 v가 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거나 같으며, 100보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 N개의 정수 중에 v가 몇 개인지 출력한다.

예제 입력 1 복사

11
1 4 1 2 4 2 4 2 3 4 4
2

예제 출력 1 복사

3

예제 입력 2 복사

11
1 4 1 2 4 2 4 2 3 4 4
5

예제 출력 2 복사

0

출처

• 문제를 만든 사람: baekjoon

풀이

1. Counting Sort

 - 공간복잡도가 더 들어간다는 단점이 있다. 하지만 범위가 -100 ~ 100이기에 201개의 배열을 잡는다면 해결이 쉽다.

 - 시간복잡도도 배열을 이용하기에 임의 접근인 O(1)으로 해결을 할 수 있다. (세어둔 이후 검색 기준)

 - 전체적인 시간 복잡도는 O(201)이 최대일 것이다.

// BaaarkingDog 실전 알고리즘 학습
// 0x03. Array
// 10807. 개수 세기
// Write : Rylah
// Date : 2022. 04. 03
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> v(202, 0);
 
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;
        v[input + 100]++;
    }
 
    int target;
    cin >> target;
 
    cout << v[target + 100] << "\n";
 
 
 
    return 0;
}
 

 

2. 이분 탐색

- 일반적인 상황에서 생각해볼 만한 이분탐색 풀이이다.

- 정렬 이후에 가장 처음에 나온 수의 위치 (lower_bound), 그 수보다 큰 수가 나온 첫 위치(upper_bound)를 이용해서 간극을 구한다.

- 다만 lower_bound가 벡터의 end를 가리킨다면, 그 수를 못찾은 것이기 때문에 0을 출력한다.

- 시간 복잡도는 O(NlogN)이다. 정렬이 모든 시간복잡도를 잡아먹는다.

- 이분탐색은 O(logN)이다.

// BaaarkingDog 실전 알고리즘 학습
// 0x03. Array
// 10807. 개수 세기
// Write : Rylah
// Date : 2022. 04. 03
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<int> v(n, 0);
 
    for (int i = 0; i < n; i++)
        cin >> v[i];
 
    sort(v.begin(), v.end());
 
    int target;
    cin >> target;
 
    if (lower_bound(v.begin(), v.end(), target) == v.end())
        cout << 0 << "\n";
    else
    {
        cout << (upper_bound(v.begin(), v.end(), target) - v.begin()) - (lower_bound(v.begin(), v.end(), target) - v.begin());
    }
    
 
 
 
    return 0;
}
 

 

위가 이분탐색 아래가 Counting Sort 풀이이다. TestCase가 작아서 메모리나 시간에서 큰 차이를 보이지 않는다.