글 읽기 - 1822 차집합 c++ 뭐가 틀린 걸까요?

roeniss 4년 전 0

얼추 다 근접했다고 생각했는데 안되서 너무 답답해요 흑흑

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a, b;
int cnt = 0;
vector<int> v;
vector<int>::iterator iter;

void binary_search(int x) {
    int low = 0, mid, high = v.size() - 1;
    int val;
    while (low <= high) {
        mid = (low + high) / 2;
        val = v[mid];
        if (val > x) {
            high = mid - 1;
        } else if (val == x) {
            cnt--;
            v[mid] = 0;
            break;
        } else { // val < x
            low = mid + 1;
        }
    }
}

int main() {
    scanf("%d %d", &a, &b);
    for (int i = 0; i < a; ++i) {
        int tmp = 0;
        scanf("%d", &tmp);
        cnt++;
        v.push_back(tmp);
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < b; ++i) {
        int tmp = 0;
        scanf("%d", &tmp);
        binary_search(tmp);
    }

    printf("%d", cnt);
    if (0 < cnt) {
        printf("\n");
        for (iter = v.begin(); iter != v.end(); ++iter) {
            int now_val = *iter;
            if (now_val > 0) printf("%d ", now_val);
        }
    }

    return 0;
}

seico75 4년 전 1

5 5
1 2 3 4 5
3 2 6 7 8

roeniss 4년 전 0

v[mid]가 두 번 다시 지나갈 일은 없을 거라고 생각했네요. 각 시행이 독립이라는 기본적인 사실을 놓치고 지나갔던 것 같습니다.

v2를 만들어서 해결하였습니다.

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

문제

문제

출처

ICPC

1822 차집합 c++ 뭐가 틀린 걸까요?

roeniss 4년 전 0

seico75 4년 전 1

roeniss 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말