글 읽기 - c++ 정렬 시간초과

dlwoqor0529 1년 전 0

ㅠㅠㅠ 도대체 ㅠㅠㅠ 왜 시간초과가 뜰까요 ㅠㅠㅠㅠ

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

using namespace std;

vector<int>a;
vector<int>b;

int binary_search(int a, vector<int> &b, int start, int end)
{
	int temp = (start + end) / 2;
	if (a == b[temp])
		return temp;
	if (a > b[temp])
		return binary_search(a, b, temp + 1, end);
	else
		return binary_search(a, b, start, temp - 1);
}

int main()
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int temp;
		cin >> temp;
		a.push_back(temp);
	}

	b = a;
	int temp = 0;
	sort(a.begin(), a.end());
	unique(a.begin(), a.end());

	for (int i = 0; i < a.size() - 1; ++i)
	{
		if (a[i] == a[i + 1])
			++temp;
	}
	
	for (int i = 0; i < b.size(); ++i)
	{
		cout << binary_search(b[i], a, 0, a.size() - temp) << ' ';
	}
}

현재 길이가 N이고 고유한 값이 M개 들어있는 정렬된 vector A가 있을 때
unique 함수에 A.begin()과 A.end()를 주면
A[0]부터 A[M-1]까지 중복제거한 값들을 정렬순서대로 채워주고
A[M]의 위치를 iterator로 반환해줍니다.
다시 말해 중복 값들을 뒤로 몰아주는 거지 실제로 날려주는 게 아닙니다.
실제로 날릴 때는 보통 erase 함수랑 같이 씁니다.

a.erase(unique(a.begin(), a.end()), a.end());

dlwoqor0529 1년 전 0

감사합니다! 함수에 대한 이해가 부족했습니다.

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

문제

문제

출처

ICPC

c++ 정렬 시간초과

dlwoqor0529 1년 전 0

zenith82114 1년 전 2

dlwoqor0529 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말