글 읽기 - 차집합 문제 이 코드가 왜 안 돌아갈까요?

whquddn55 6년 전 0

분명히 문제 조건에 INT_MAX이하의 "자연수"라고 하였기에 lower_bound로 체크하여 같은 원소 발견하면 0으로 바꾸어주어 checked배열없이 처리하려고 제출했으나 7%에서 틀렸다고 나옵니다.

딱 하나, checked배열로 체크해주느냐, arrA에 0을 넣어서 체크해주느냐 차이인데 왜 틀렸다고 나올까요?

혹시나 자연수 범위가 아니라 INT_MIN~ INT_MAX일까봐 long long으로 바꾸고 LLONG_MAX로 체크해주어도 7%에서 틀렸습니다가 뜹니다.

// 7%에서 틀렸습니다

#include <bits/stdc++.h>
using namespace std;
#define INF (INT_MAX / 2)
typedef pair<int, int> pii;

vector<int> arrA;
int nA, nB;

int main() {
	scanf("%d %d", &nA, &nB);
	arrA.resize(nA);
	for (int i = 0; i < nA; i++) 
		scanf("%d", &arrA[i]);
	sort(arrA.begin(), arrA.end());

	int cnt = nA;
	for (int i = 0; i < nB; i++) {
		int element;
		scanf("%d", &element);

		int index = lower_bound(arrA.begin(), arrA.end(), element) - arrA.begin();
		if (index < nA && arrA[index] == element) {
			arrA[index] = 0;
			cnt--;
		}
	}
	printf("%d\n", cnt);
	for (int i = 0; i < nA; i++)
		if (arrA[i] != 0)
			printf("%d ", arrA[i]);

	return 0;
}

// 한끝차이인데 왜...?
/*******************************************/

#include <bits/stdc++.h>
using namespace std;
#define INF (INT_MAX / 2)
typedef pair<int, int> pii;

vector<int> arrA;
bool checked[500001];
int nA, nB;

int main() {
	scanf("%d %d", &nA, &nB);
	arrA.resize(nA);
	for (int i = 0; i < nA; i++) 
		scanf("%d", &arrA[i]);
	sort(arrA.begin(), arrA.end());

	int cnt = nA;
	for (int i = 0; i < nB; i++) {
		int element;
		scanf("%d", &element);

		int index = lower_bound(arrA.begin(), arrA.end(), element) - arrA.begin();
		if (index < nA && arrA[index] == element) {
			checked[index] = true;
			cnt--;
		}
	}
	printf("%d\n", cnt);
	for (int i = 0; i < nA; i++)
		if (!checked[i])
			printf("%d ", arrA[i]);

	return 0;
}

sanghyun1210 4년 전 1

제 짧은 식견으로는..

0을 대입하게되면 sort를 한 의미가 사라져서 그렇지 않을까 싶네요

처음 원소는 상관없겠지만, 0이 추가됨에 따라 정렬이 안되있는 상태에서 lower_bound를 진행하는것이 문제가 아닐까 싶습니다.

whquddn55 4년 전 1

뽀시래기일 때 쓴 글인데 늦게나마 답변주셔서 감사합니다 ㅎㅎ 지금보니 부끄럽네요

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

문제

문제

출처

ICPC

차집합 문제 이 코드가 왜 안 돌아갈까요?

whquddn55 6년 전 0

sanghyun1210 4년 전 1

whquddn55 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말