1-L 이분탐색 풀이 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-L

작성

112

수정됨

안녕하세요, 1-L 문제 이분탐색으로 풀어보았는데요.

lower_bound함수는 목표값을 찾지 못하면 해당 벡터 끝 다음 이터레이터 즉 코드상 arr.end()를 반환하니 lower_bound 실행 후 arr.end()인지 아닌지만 체크해주면 값을 찾았다로 생각했습니다. 그러나 실행시켜보니 조건문에 추가로 &&*it == goal를 적어주어야 성공이고 밑에 첨부한 링크와 같이 이 과정을 생략한다면 틀렸습니다라고 나옵니다. 이유를 알 수 있을까요?

http://boj.kr/7f90a9926f17477394e238b900523acc

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 인서님 ㅎㅎ

이런 코드를 원하셨던게 아닐까요?

제가 다듬어 봤습니다.

#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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

송인서

질문자

네 맞습니다.

하지만 제가 궁금한 점은 보내주신 코드에서 마지막 조건문 중 *it == goal부분을 지우고 제출해도 맞았다고 채점되어야 할 것 같은데 아니어서 질문한 것이었습니다!

lower_bound 함수의 결과인 it이 arr.end()인지 아닌지만 확인하면 되는것 아닌가요?(arr.end()가 아니라면 목표값을 찾았다는것을 의미하기에..)

큰돌

지식공유자

안녕하세요 ㅎㅎ

(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-L 이분탐색 풀이 질문