[백준 11652] 카드

문제출처: https://www.acmicpc.net/problem/11652

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 <= N <= 1000000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

풀이

정답률이 많이 낮습니다.. 문제분류가 정렬인데 사실 정렬은 sort함수만 써도되니 그건아닌것 같고.. 아마도 가장 많이 갖고있는 수를 구하는 과정에서 어려움을 겪으셨을겁니다. 

일단 입력범위를 보니, 그리고 많이갖고있을 떄 작은 수를 출력하라는 조건에 의해  long long 형의 100만크기의 배열을 선언합시다. 그리고 sort함수로 정렬해요.(퀵정렬은 최악의 경우 O(n^2)이므로 시간초과가 날 수 있지만 sort함수의 평균적 시간복잡도는 O(nlogn)입니다. 찝찝하시면 병합정렬쓰세요! 그리고 이제 답을구하기 위해 변수를 선언합시다. cnt는 연속된 수의 개수를(주의: 0으로 초기화 할시 1 1 1 2 일때 2개가됩니다.) , max는 가장 큰 연속된 개수의 수, index는 가장 큰 연속된 개수를 가질 때 그 위치의값을 나타냅니다. 그리고, 수가 연속될 때, 연속되지 않을 떄의 2가지경우로 나누어서 숫자를 세봅시다. 일단 연속되지않으면 무조건 cnt를 1로 초기화합니다.(0으로 초기화하면 안됩니다. 위에서 얘기했듯이 1 1 1 2 일때 2개가 되죠.)연속될 시, cnt를 한칸 증가시켜주고 max값을 갱신해줍니다. 갱신해 줄 때 그 때의 index를 저장합니다.최종적으로 반복문을 마치고 card[index]가 정답이됩니다. 최종적으로 시간복잡도는 O(nlogn)+O(n)입니다. 그리고 마지막으로,, 아래 채점결과에서 볼 수 있듯이 c++의 입출력함수가 시간을 많이 잡아먹으므로 cin.tie(0); cin.sync_with_stdio(false); 선언을 생활화 합시다.

주의 할것 : 

cnt= 1로 초기화하고 조건식에서 연속되지않을 시 0이 아닌 1로 초기화하기

c++ 입출력 사용 시 개행을 '\n', 입출력 시 cin.tie(0); cin.sync_with_stdio(false); 선언 생활화하기

코드

채점결과 순서대로 각각 

개행:'\n', cin.tie(0),cin.sync_with_stdio(false)선언했을 때 : 28ms

개행:'\n'만 썼을 때 : 120ms

c++입출력사용했을 때 : 136ms

#include<iostream>
#include<algorithm>
using namespace std;
long long card[1000000];
int main()
{
	int n;
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> card[i];
	sort(card, card + n);
	//세기위한 변수, 갯수를 비교하기위한변수
	int cnt = 1, max = 0, index = 0;
	for (int i = 0; i < n - 1; i++)
	{
		if (card[i] == card[i + 1])
		{
			cnt++;
			if (cnt > max)
			{
				max = cnt;
				index = i;
			}
		}
		else
			//0이아닌 1로초기화!
			cnt = 1;
	}
	cout << card[index] << '\n';
	
}

 

결과