[pat 연습문제] 3개.

제목 링크:https://www.nowcoder.com/pat/1/problems
1001.Rational Sum
바로 점수를 누적하여 0/1로 누적한다. 넘칠 때마다 한 번씩 약분하는 것을 방지하기 위해 최대 공약수를 구하려면 전전상제법을 사용한다. 제목에 규정된 출력의 마이너스 번호는 분자에만 있을 수 있기 때문에 분모에 마이너스 번호가 있는 것을 방지하기 위해 처리를 한다. 코드는 다음과 같다.

#include
#include
using namespace std;

typedef long long ll;

//              
int gcd(int x, int y)
{
	return y ? gcd(y, x % y) : x;
}

int main()
{
	ll a = 0, b = 1; // a    ， b    
	ll c, d;    // c    ， d    
	char flag;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> c >> flag >> d;
		ll aa = a*d + b*c;
		ll bb = b*d;
		ll g = gcd(aa, bb);
		a = aa / g;
		b = bb / g;
	}
	
	ll x = a / b; //        
	ll y = a % b; //           

	if (b < 0)
	{
		a = -a; //       
		b = -b;
	}

	if (a == 0)
	{
		cout << 0;
	}
	else if (x == 0)
	{
		cout << a << "/" << b;
	}
	else
	{
		cout << x << " ";
		if (y != 0)
		{
			cout<< y << "/" << b;
		}
	}
	return 0;
}

1003.List Grades
이 문제는 바로 정렬이다. 통 정렬 공간을 사용하여 시간을 바꾸어 시간 복잡도 O(1)를 만든 다음에 큰 것부터 작은 것까지 출력한다. 사실은 우선 대기열로 폭력적으로 출력할 수 있다. 그러나 나는 복잡도가 너무 크다고 생각한다. 코드는 다음과 같다.

#include
#include
#include
using namespace std;
int main()
{
    vectorname(102);
    vectorid(102);
    vectorgrade(102);  //   
    int n;
    cin>>n;
    int temp;
    for(int i = 1 ; i <= n; i++)
    {
        cin>>name[i]>>id[i]>>temp;
        grade[temp] = i;
    }
    int min;
    int max;
    cin>>min;
    cin>>max;
    int flag = false;
    for(int i = max ; i >= min; i--)
    {
        if(grade[i] > 0)
        {
            flag = true;
            cout<

1005.The Dominant Color
이 문제는 m*n의 데이터에서 가장 많이 나오는 수를 찾는 것이다. 나는 맵으로 저장한 다음에 우선 대기열에 넣는다. (우선 대기열은 첫 번째 파라미터가 크고 작은 자동 정렬까지) 가장 큰 것을 출력하면 된다. 간단하고 거칠다. 코드는 다음과 같다.

#include
#include
#include
#include
#include
using namespace std;

int main()
{
	unordered_map map;
	int m, n, temp;
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> temp;
			map[temp]++;
		}
	}
	priority_queue> pq;
	for (auto it = map.begin(); it != map.end(); it++)
	{
		pq.push(make_pair(it->second, it->first));
	}
	cout << pq.top().second;
	return 0;
}