-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
1-L 이분탐색 풀이 질문
24.07.04 21:28 작성 24.07.04 21:44 수정 조회수 53
0
안녕하세요, 1-L 문제 이분탐색으로 풀어보았는데요.
lower_bound함수는 목표값을 찾지 못하면 해당 벡터 끝 다음 이터레이터 즉 코드상 arr.end()를 반환하니 lower_bound 실행 후 arr.end()인지 아닌지만 체크해주면 값을 찾았다로 생각했습니다. 그러나 실행시켜보니 조건문에 추가로 &&*it == goal를 적어주어야 성공이고 밑에 첨부한 링크와 같이 이 과정을 생략한다면 틀렸습니다라고 나옵니다. 이유를 알 수 있을까요?
답변을 작성해보세요.
0
큰돌
지식공유자2024.07.05
안녕하세요 인서님 ㅎㅎ
이런 코드를 원하셨던게 아닐까요?
제가 다듬어 봤습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> arr;
int ans;
int main()
{
cin >> n >> m;
for (int i = 0, tmp; i < n; i++)
{
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
for (int i = 0; i < n; ++i)
{
int k = arr[i];
int goal = m - k;
//i + 1 부터 찾아야하지 않을까요? 중복되게 검사가 가능 -> 해제 -> ans / s를 안해도 됨.
auto it = lower_bound(arr.begin() + i + 1, arr.end(), goal);
//*it 로도 가능.
if (it != arr.end() && *it == goal)
ans++;
}
cout << ans;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
송인서
질문자2024.07.05
네 맞습니다.
하지만 제가 궁금한 점은 보내주신 코드에서 마지막 조건문 중 *it == goal부분을 지우고 제출해도 맞았다고 채점되어야 할 것 같은데 아니어서 질문한 것이었습니다!
lower_bound 함수의 결과인 it이 arr.end()인지 아닌지만 확인하면 되는것 아닌가요?(arr.end()가 아니라면 목표값을 찾았다는것을 의미하기에..)
큰돌
지식공유자2024.07.06
안녕하세요 ㅎㅎ
(arr.end()가 아니라면 목표값을 찾았다는것을 의미하기에..)
>> 이부분에 대한 생각이 틀리신 것 같습니다.
lower_bound에 대한 내용이 있는 부분입니다.(교안)
lower_bound는 해당 값이상인 부분을 찾아 반환합니다.
예를 들어 lower_bound로 1을 찾는다고 했을 때 다음과 같은 경우는 2를 가리키는 0을 반환하게 됩니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
vector<int> a {2, 2, 3, 3, 3, 4};
cout << &*lower_bound(a.begin(), a.end(), 1) - &*a.begin()<< "\n";
return 0;
}
/*
0
*/
그래서 *it == goal 부분이 필요합니다.
답변 1