BOJ 11652. 카드

BOJ 11652. 카드

2022. 11. 14. 20:37ㆍ공부/알고리즘

11652번: 카드

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

www.acmicpc.net

이 문제는 언듯 보면 카운팅 정렬 문제라고 생각할 수 있다.

그러나 수의 범위가 2*2**62 이므로 엄청나게 큰 배열이 필요하다.

당연히 카운팅 소트를 이용하려들면 실패한다.

이 문제의 경우 정렬을 이용하면 된다.

만약 다음처럼 무작위 배열이 존재한다고 가정하자

1 4 2 4 5 3 4 2 2 2 1 4

이를 정렬하게되면

1 1 2 2 2 2 3 4 4 4 4 5

가 되고, 앞에서부터 개수를 세가며 제일 많은 숫자를 토출하면 된다.

여기서 마지막에 도착했을 때를 따로 정의해주어야 모든 숫자를 비교하여 반영하게 되는 점을 주의해야한다.

Riam