백준/11652/sort||map/카드

백준/11652/sort||map/카드
sort 또는 map을 사용해야 하는 문제입니다.

적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다.

일단 이 지문을 통해 배열을 int type으로 선언하지 않아야하는것을 알 수 있습니다.

signed int type range: -2^31 ~ 2^31-1

일단 값을 받는 배열은 long long type으로 받습니다. 받을 수 있는 숫자의 최대 범위까지 큰 배열을 선언해 counting_sort를 통해 배열의 포함된 요소들의 수를 계산하고 다시 최대 값을 배열에서 끄집어 내면되는데 이는 시간 초과가 발생합니다.

그래서 우선 sort함수로 배열을 정열하여 같은 수들은 나열되도록 정리하였습니다.

	max_num = arr[0];

	for (int i = 1; i < N; i++) {
		if (max_num != arr[i])
			break;
		max_count++;
	}

이렇게 우선 max_num, max_count를 초기화합니다.

	int tmp = max_count;
	int compare_count = 1;
	long long compare_num = arr[tmp];

그 다음 max_num과 비교할 compare_num을 초기화 해줍니다.
arr[max_cout] 즉, arr[max_count-1]까지가 arr[0]과 같은 수들이 나오는 인덱스이고
max_count 인덱스 부터 arr[0]과 다른 수가 나오니 compare_num=arr[max_count]을 주고
compare_count도 1증가 시켜줍니다.

	for (int i = tmp + 1; i < N; i++) {
		if (compare_num != arr[i]) {
			compare_num = arr[i];
			compare_count = 1;
		}
		else {
			compare_count++;
			if (compare_count > max_count) {
				max_num = arr[i];
				max_count = compare_count;
			}
		}
	}

이제 tmp 즉, max_count 넘어서부터 for문을 돌려서 compare_num과 다르면 새로운 숫자가 나온것이니 compare_num과 compare_count를 다시 초기화 해주고
아니면 compare_count를 계속 증가시켜줍니다. 이 때 max_count보다 높으면 compare_num이 max_num보다 더 많이 나온 수가 되니 max_num를 교체해주고
max_count 역시 compare_num으로 교체해줍니다.

풀이

1. 첫번째 풀이

#include<iostream>
#include<algorithm>
using namespace std;

long long arr[100000];
int N;
long long max_num;
int max_count = 1;

void func() {
	for (int i = 1; i < N; i++) {
		if (max_num != arr[i])
			break;
		max_count++;
	}

	int tmp = max_count;
	int compare_count = 1;
	long long compare_num = arr[tmp];

	for (int i = tmp + 1; i < N; i++) {
		if (compare_num != arr[i]) {
			compare_num = arr[i];
			compare_count = 1;
		}
		else {
			compare_count++;
			if (compare_count > max_count) {
				max_num = arr[i];
				max_count = compare_count;
			}
		}
	}

	cout << max_num;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);
	max_num = arr[0];
	func();
}