글 읽기 - lower_bound, upper_bound 질문 드립니다.

adh30 4년 전 0

안녕하세요.

10816번을 이분탐색을 구현하여 풀어보려고 했지만, 예외 처리를 어떻게 해야될 지 몰라 답을 검색하던 중 lower_bound , upper_bound에 대해 알게되었습니다.

이 또한 이분 탐색으로 구현되어 있다고 들어 적용해보니 통과할 수 있었습니다.

궁금한점은

int arr[5] = {1,2,3,4,5} 이러한 배열에서 lower_bound로 100을 찾으려고 했을 경우에 쓰레기 값이 나옴을 확인했는데 이 문제에는 왜 통과하는지 모르겠습니다.. 테스트 케이스에 이러한 경우가 없는것인가요? 아니면 제가 모르는 lower_bound의 무언가가 있을까요 ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> v;
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int temp;
		scanf("%d", &temp);
		v.push_back(temp);
	}
	sort(v.begin(), v.end(), less<int>());
	
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int findAns;
		scanf("%d", &findAns);
		vector<int>::iterator low, up;
		low = lower_bound(v.begin(), v.end(), findAns);
		up = upper_bound(v.begin(), v.end(), findAns);
		
		printf("%d ", up - low);
	}
}

djm03178 4년 전 0

질문 내용과 코드가 다른데, 질문 내용처럼 int 배열인 경우 그냥 arr[5]를 가리키는 포인터가 반환되고, 코드처럼 vector<int>인 경우 v.end()가 반환됩니다. 어느 쪽이든 반환된 주소 / iterator가 가리키는 원소의 값을 사용하는 게 아니라 단순히 거리를 구하는 것이기 때문에 쓰레기값이 있어도 상관 없습니다.

adh30 4년 전 0

아.. 생각을 잘못 했었습니다.. 실수가 많은 질문임에도 답변 해주셔서 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

lower_bound, upper_bound 질문 드립니다.

adh30 4년 전 0

djm03178 4년 전 0

adh30 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말