[백준 11652] - 카드 Python

https://www.acmicpc.net/problem/11652

 

문제 풀이 전략

숫자의 범위가 -2^{62}$부터 2^{62}$로 매우 넓지만, 카드의 개수 N은 10만 개라는 점에 주목했다. 숫자의 범위를 인덱스로 사용하는 계수 정렬은 메모리 초과로 불가능하므로, 데이터를 리스트에 담아 정렬한 뒤 순차적으로 탐색하는 전략을 세웠다.

 

추상화된 흐름

1. 데이터 수합 및 정렬: 입력받은 $N$개의 카드를 리스트에 저장하고 오름차순으로 정렬한다. 이렇게 하면 같은 숫자의 카드들이 이웃하게 배치된다.
2. 선형 탐색(Linear Scan): 리스트를 한 번 훑으면서 인접한 두 카드가 같은지 확인하여 연속된 개수를 센다.
3. 최빈값 갱신: 현재까지 센 개수가 기존의 최대 개수보다 많을 때만 정답 변수를 갱신한다.
   • 시간 복잡도: 정렬에 O(N \log N)$, 탐색에 $O(N)$이 소요되어 최종적으로 O(N \log N)$에 해결 가능하다.

해결 과정

1. 입력값 처리: int(input())을 사용하여 큰 정수 범위의 데이터를 안전하게 입력받는다.
2. 리스트 정렬: cards.sort()를 통해 오름차순 정렬을 수행한다.
3. 변수 초기화:
   • max_number: [가장 많이 나온 숫자, 등장 횟수]를 저장 (초기값: [cards[0], 1])
   • count: 현재 확인 중인 숫자의 연속 등장 횟수 (초기값: 1)
4. 반복문 수행: 0번 인덱스부터 len(cards)-1까지 인접한 원소를 비교하며 count를 누적하고, 더 큰 count가 발견될 때마다 max_number를 업데이트한다.

 

어려웠던 점 및 복기

어려웠던 점은 딱히 없었지만 알고리즘을 너무 많이 쉬었던게 푸는 시간으로 체감이 되서 만족스럽지는 않았다.

 

 

전체 코드