글 읽기 - lower_bound 이용한 풀이 뭐가 잘못되었을까요?

shklaurant 1년 전 0

직접 이분 탐색 코드를 쓰지 않고 lower_bound이용해서 풀어보려 했는데 계속 틀리네요;;

어느 부분이 잘못되었을까요?

#include <bits/stdc++.h>

using namespace std;

int t, n, m;

vector<int> n1;
vector<int> n2;

void sol() {
    sort(n1.begin(), n1.end());
    for (auto &el: n2) {
        auto it = lower_bound(n1.begin(), n1.end(), el);
        if (it == n1.end()) {
            el = 0;
        } else if (it == n1.begin()) {
            *it == el ? el = 1 : el = 0;
        } else {
            el = 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;

    for (auto i = 0; i < t; ++i) {
        n1.clear();
        n2.clear();

        cin >> n;
        n1.resize(n);
        for (auto &el: n1) {
            cin >> el;
        }

        cin >> m;
        n2.resize(m);
        for (auto &el: n2) {
            cin >> el;
        }

        sol();

        for (auto el: n2) {
            cout << el << '\n';
        }
    }

    return 0;
}

kokosoko59 1년 전 0

16번 조건문을 저렇게 쓰신 이유가 뭔가요? 아마도 저게 문제인것 같습니다.

shklaurant 1년 전 0

n1.begin() 이 리턴값인 경우 다음 2가지 경우의 수가 있다고 생각했습니다.

1. 배열의 모든 수가 el 보다 크다

2. 정말 첫번째 수가 el이다

그래서 3항 연산자로 한번더 거르는 코드인데요... 제가 잘못 알고 있는건가요?

kokosoko59 1년 전 1

그렇다면 16번째 줄이 아니라 18번째 줄에 뭔가 더 추가해야겠네요.

지금 코드는 it가 맨처음, 맨끝일때만 el에 0이 들어갈 수 있고 it가 배열의 중간에 있을때는 무조건 1이 들어가게 되어있습니다.

하지만 it는 배열의 중간이면서 수첩1에는 없는 값일 수도 있습니다.

shklaurant 1년 전 1

아 해당 부분이 문제였네요! 고치고 제출하니 잘 됩니다. 감사합니다!

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

문제

문제

출처

ICPC

lower_bound 이용한 풀이 뭐가 잘못되었을까요?

shklaurant 1년 전 0

kokosoko59 1년 전 0

shklaurant 1년 전 0

kokosoko59 1년 전 1

shklaurant 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말