https://www.acmicpc.net/status?user_id=jjune0461&problem_id=10816&from_mine=1
채점 현황
www.acmicpc.net
이번 문제는 처음에 그냥 생각나는 가장 쉬운 방법은 프루트포스로 시작을 했습니다.
솔직히 난이도에 맞지 않는 것은 확실하지만 그냥 해보았고 역시나 시간초과가 발생했습니다.
그 다음에 생각을 한 방법은 이진 탐색이었습니다.
이진탐색으로 하려고 생각을 하다가 만약에 상황이 다음과 같다고 가정을 해봅시다.
1 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 5 |
이렇게 되어있다면 같고 싶은 값이 3이라고 했을 때
이진 탐색을 통해서 3을 찾는다면 중앙값이 3인데 앞, 뒤로 얼만큼 더 가야하는지 코딩하기가 너무 어려울 것 같다는
생각을 하게되었습니다.
다양한 방식으로 생각을 해보다가 결국 인터넷에 찾아보게 되었습니다.
제가 모르는 algorithm헤더에 존재하는 upper_bound, lower_bound를 발견했습니다.
Upper_bound & Lower_bound
간단하게 설명드리겠습니다.
upper_bound: 찾고 싶은 값을 초과하는 값이 처음 나오는 인덱스의 주소값 (<)
lower_bound: 찾고 싶은 값 이상의 값이 처음 나오는 인덱스의 주소값 (<=)
그렇다면 다시 저 배열을 예시로 들어보겠습니다.
1 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 5 |
여기서 3을 초과하는 인덱스가 몇번째 인덱스인지 알고 싶다면 아래처럼 해줘야한다.
lower_bound(a.begin(), a.end(), positions[i]) - a.begin()
lower_bound가 주소값이 나오게 되서
초과하는 값을 처음 찾은 주소 - 1번 인덱스의 주소 를 한다면 몇번째에 있는지 나오게 된다.
다른 예시로 여기서 찾고 싶은 값이 3이라고 합시다. 그리고 3이 총 몇번이나 있는지 구하고 싶습니다.
그렇다면 다음과 같이 작성하면 됩니다.
(위 값들은 vector container안에 선언이 되어있으며 vector의 이름은 a입니다.)
cout << upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3) << endl;
초과하는 인덱스가 처음 나오는 곳은 4가 존재하는 '8'입니다.
이상인 인덱스가 처음 나오는 곳은 3이 처음 존재하는 '2'입니다.
이러한 생각을 잡으면 다른 방식의 문제도 쉽게 풀 수 있습니다.
예시를 들어보자면
"3이상 8미만의 수가 몇번 나오나요?" 와 같은 문제를 예시로 들 수 있습니다.
아직 제가 공부하지 못한것은 lower_bound & upper_bound의 return값을 명확하게 모르겠었습니다.
그래서 auto를 쓸까? 아니면 그냥 count에 출력을 할까 생각을 해보았는데 cout에서 계산(-)이 잘 되어서 출력이 되는 것을 보고 출력을 하는 방식으로 선택했습니다.
문제 풀이 코드
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N, M;
int main(int argc, const char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N; //N은 상근이가 가지고 있는 숫자 카드의 개수, M은 숫자 카드의 종류 갯수
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
cin >> M; //M만큼 받아옴
for (int i = 0; i < M; i++) {
int number;
cin >> number;
//int l = lower_bound(a.begin(), a.end(), number);
//int u = upper_bound(a.begin(), a.end(), number);
cout << upper_bound(a.begin(), a.end(), number) - lower_bound(a.begin(), a.end(), number) << " ";
}
}
'백준 문제 풀이 & C++ 공부' 카테고리의 다른 글
백준 10845번 C++ (0) | 2021.08.29 |
---|---|
백준 10828번 C++ (0) | 2021.08.19 |
백준 10814번 C++ (0) | 2021.07.07 |
C++ sort & stable_sort (0) | 2021.07.07 |
C++ Vector Container (0) | 2021.07.05 |