๋ฌธ์
11663๋ฒ: ์ ๋ถ ์์ ์
์ฒซ์งธ ์ค์ ์ ์ ๊ฐ์ N๊ณผ ์ ๋ถ์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. (1 ≤ N, M ≤ 100,000) ๋์งธ ์ค์๋ ์ ์ ์ขํ๊ฐ ์ฃผ์ด์ง๋ค. ๋ ์ ์ด ๊ฐ์ ์ขํ๋ฅผ ๊ฐ์ง๋ ๊ฒฝ์ฐ๋ ์๋ค. ์ ์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ์ ๋ถ์ ์์์ ๊ณผ
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, M; cin>>N>>M;
vector<int> v;
for(int i=0; i<N; i++){
int inp; cin>>inp;
v.push_back(inp);
}
sort(v.begin(), v.end());
for(int i=0; i<M; i++){
int a, b; cin>>a>>b;
int first = lower_bound(v.begin(), v.end(), a) - v.begin();
int second = upper_bound(v.begin(), v.end(), b) - v.begin();
cout<<second - first<<'\n';
}
}
ํ์ด
๊ทธ๋ฅ a์ด์ b์ดํ์ธ ๊ฐ์ ๊ฐ์๊ฐ ๋ช ๊ฐ์ธ์ง ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
upper_bound๋ฅผ ์ฌ์ฉํด์ b๋ณด๋ค ํฐ ๊ฐ์ ์ฒซ ์ธ๋ฑ์ค๋ฅผ ์ฐพ๊ณ
lower_bound๋ฅผ ์ฌ์ฉํด์ a๋ณด๋ค ๊ฐ๊ฑฐ๋ ํฐ ์ฒซ ์ธ๋ฑ์ค๋ฅผ ์ฐพ์ต๋๋ค.
๋ฐ๋ผ์ upper_bound_index - lower_bound_index๋ฅผ ํ๋ฉด a์ด์ b์ดํ์ธ ๊ฐ์ ๊ฐฏ์๋ฅผ ์ ์ ์์ต๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 6236๋ฒ - ์ฉ๋ ๊ด๋ฆฌ (0) | 2022.09.08 |
---|---|
[๋ฐฑ์ค,c++] 20040๋ฒ - ์ฌ์ดํด ๊ฒ์ (0) | 2022.09.07 |
[๋ฐฑ์ค,c++] 11561๋ฒ - ์ง๊ฒ๋ค๋ฆฌ (0) | 2022.09.07 |
[๋ฐฑ์ค,c++] 17136๋ฒ - ์์ข ์ด ๋ถ์ด๊ธฐ (0) | 2022.09.06 |
[๋ฐฑ์ค,c++] 2533๋ฒ - ์ฌํ๋ง ์๋น์ค(SNS) (0) | 2022.09.04 |
[๋ฐฑ์ค,c++] 15681๋ฒ - ํธ๋ฆฌ์ ์ฟผ๋ฆฌ (0) | 2022.09.04 |
๋๊ธ