[소프티어] 자동차 테스트

Kim Yuhyeon·2023년 10월 10일

알고리즘

알고리즘 + 자료구조

목록 보기

141/161

문제

https://softeer.ai/practice/info.do?idx=1&eid=1717&sw_prbl_sbms_sn=266595

접근 방법

m보다 작은 개수 * m보다 큰 개수를 반환하는 문제
lower_bound를 이용하였다.

풀이

1번째 : 시간초과


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

using namespace std;

int n, q;
vector<int> carVec; // 자동차 연비 벡터
vector<int> qVec; // 질의 벡터 

void FastIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}


void Input()
{
	// 첫 번째 줄에 n, q가 공백을 사이에 두고 주어집니다.
	cin >> n >> q;

	int x;
	// 두 번째 줄에는 n개의 자동차의 연비에 해당하는 값이 공백을 사이에 두고 주어집니다.
	for(int i=0; i<n; i++)
	{
		cin >> x;	
		carVec.push_back(x);
	}

	int m;
	// 세 번째 줄부터는 q개의 줄에 걸쳐 테스트 결과로 기대하는 값인 mi가 한 줄에 하나씩 주어집니다.
	for(int i=0; i<q; i++)
	{
		cin >> m;
		qVec.push_back(m);
	}
}

void Solve()
{
	// 오름차순 정렬 
	sort(carVec.begin(), carVec.end());


	for(int q : qVec)
	{
		if (find(carVec.begin(), carVec.end(), q) == carVec.end())
		{
			cout << 0 << '\n';
			continue;
		}

		// q보다 작은 개수 * 큰 개수 
		int lowerCnt = lower_bound(carVec.begin(), carVec.end(), q) - carVec.begin(); 
		int upperCnt = n - (upper_bound(carVec.begin(), carVec.end(), q) - carVec.begin());

		cout << lowerCnt * upperCnt << '\n';
	}
	
}


int main(int argc, char** argv)
{
	FastIO();
	Input();
	Solve();
	return 0;
}

처음에 벡터에 주어진 q가 없을 때를 찾기 위해 find를 썼었으나
시간초과가 되어 수정하였다.
(q 반복문 : 200,000개) * (find에서 최대 개수 : 50,000)이라 시간 초과가 났던 듯 하다.

2번째 : 통과

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

using namespace std;

int n, q;
vector<int> carVec; // 자동차 연비 벡터
vector<int> qVec; // 질의 벡터 

void FastIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}


void Input()
{
	// 첫 번째 줄에 n, q가 공백을 사이에 두고 주어집니다.
	cin >> n >> q;

	int x;
	// 두 번째 줄에는 n개의 자동차의 연비에 해당하는 값이 공백을 사이에 두고 주어집니다.
	for(int i=0; i<n; i++)
	{
		cin >> x;	
		carVec.push_back(x);
	}

	int m;
	// 세 번째 줄부터는 q개의 줄에 걸쳐 테스트 결과로 기대하는 값인 mi가 한 줄에 하나씩 주어집니다.
	for(int i=0; i<q; i++)
	{
		cin >> m;
		qVec.push_back(m);
	}
}

void Solve()
{
	// 오름차순 정렬 
	sort(carVec.begin(), carVec.end());

	// 200,000개
	for(int q : qVec)
	{

		// q보다 작은 개수 * 큰 개수 
		// idx + 1(q) + idx2 = n
		// idx2 = n - 1(q) - l 

		// q보다 같거나 작은 인덱스 반환 
		int idx = lower_bound(carVec.begin(), carVec.end(), q) - carVec.begin(); 

		// carVec[idx] == q이면 벡터 안에 존재, idx가 n이
		if (carVec[idx] == q && idx != n)
			cout << idx * (n-idx-1) << '\n';
		
		else 
			cout << 0 << "\n";
	}
	
}


int main(int argc, char** argv)
{
	FastIO();
	Input();
	Solve();
	return 0;
}

upper_bound를 하는 대신 lower_bound를 한번만 해서 단순 뺄셈으로 큰 개수를 구하도록 하였다.
벡터 내에 q 가 존재하는지 판별 방법
: find 대신에 upper_bound에서 나온 인덱스 값이 q 와 불일치하면 벡터 내에 존재하지 않는다고 판단하여 0을 출력하도록 하였다.