글 읽기 - 코드 질문이용...

jumpingz 6년 전 0

예전에 푼 소스가 왜 맞는지 이해가 안가네요.

도현이가 만든 소스에 아래와 같은 샘플을 넣었는데요

1 1 1

도현이가 만든 소스에 위 샘플을 넣으면 0 이 나오는데

제가 맞은코드는 lower_bound 를 이용한 코드라 2가 출력됩니다.

같은 데이터가 존재할 때 값이 변형되는걸 방지하기 위해 이진탐색을 이용해서 다르게 처리했는데요. 오히려 이방법이 틀렷다고 뜨네요.. 뭐가 문제인지 알 수 있을까요??

// lower_bound 이용하여 맞은 소스
#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	
	int i, N , max = -1, *A , *B;
	cin >> N;

	A = new int[N];	B = new int[N];

	for (i = 0; i < N; i++)
	{
		cin >> A[i];
		B[i] = A[i];
	}
	sort(B, B + N);
    
	for (i = 0; i < N; i++)
	{
		if (i - (lower_bound(B, B + N, A[i]) - B) > max)
			max = i - (lower_bound(B, B + N, A[i]) - B);
	}
	cout << max;
	delete[] A;	delete[] B;
	return 0;
}

// binary_search 를 이용했는데 틀린 소스
#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int Binary_Search(vector< pair<int, int> > &T, int s, int e, int key, int order);

int main()
{
	int N, result = 0;
	scanf("%d", &N);

	vector<int> v(N + 1);
	vector< pair<int,int> > T(N + 1);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &v[i]);
		T[i].first = v[i];
		T[i].second = i;
	}
		
	sort(T.begin(), T.end());
	for (int i = 1; i <= N; i++)
	{
		int p = Binary_Search(T, 1, N , v[i], i);

		if (result < i - p)
			result = i - p;
	}

	printf("%d", result);
	return 0;
}

int Binary_Search(vector< pair<int,int> > &T, int s, int e, int key, int order)
{
	while (s <= e)
	{
		int mid = (s + e) >> 1;

		if (T[mid].first > key)
			e = mid - 1;
		else if (T[mid].first < key)
			s = mid + 1;
		else
		{
			if (T[mid].second > order)
				e = mid - 1;
			else if (T[mid].second < order)
				s = mid + 1;
			else
				return mid;
		}
	}
	
	return -1;
}

pyw0564 5년 전 0

안녕하세요 선배님

1 부터 N까지 받으셔서

배열 [0] 에 0이 들어가서 그렇습니다.

#include <iostream>
#include <algorithm>
#include <assert.h>
#include <cstdio>
#include <vector>
using namespace std;

int Binary_Search(vector<int> &T, int s, int e, int key)
{
	while (s <= e)
	{
		int mid = (s + e) / 2;

		if (T[mid] > key)
			e = mid - 1;
		else if (T[mid] < key)
			s = mid + 1;
		else
			return mid;
	}
	assert(true);
	return -1;
}
int main()
{
	int N, ret = 0;
	scanf("%d", &N);

	vector<int> v(N);
	vector<int> T(N);
	for (int i = 0; i < N; i++)
		scanf("%d", &v[i]);

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

	for (int i = 0; i < N; i++)
	{
		int p = Binary_Search(T, 0, N - 1, v[i]);
		ret = max(ret, i - p);
	}

	printf("%d", ret);
	return 0;
}

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

문제

문제

출처

ICPC

코드 질문이용...

jumpingz 6년 전 0

pyw0564 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말