ps:problems:codeforces:1665b
Array Cloning Technique
| ps | |
|---|---|
| 링크 | codeforces.com/… |
| 출처 | Codeforces |
| 문제 번호 | 1665B |
| 문제명 | Array Cloning Technique |
| 레벨 | 900 |
| 분류 |
기본 |
| 시간복잡도 | O(nlogn) |
| 인풋사이즈 | n <= 10^5 |
| 사용한 언어 | PyPy 3.10 |
| 제출기록 | 13500KB / 125ms |
| 최고기록 | 93ms |
| 해결날짜 | 2026/05/17 |
- 처음 주어진 배열의 원소들 중에서, 가장 빈도수가 높은 원소로 다른 모든 원소들을 바꿔주는게 최선이다.
- 가장 빈도수가 높은 원소가 x, 그 빈도수가 k라고 하면, 필요한 연산의 횟수는 시뮬레이션으로 구할수 있다. 수열을 클론하고 → 클론한 수열의 모든 x를 스왑해서 빈도수를 2k로 만들고 → 다시 그 수열을 클론하고 → 2k번 스왑해서 빈도수를 4k로 만들고 → … 이것을 반복하면 된다. 시간복잡도는 O(logn) 이다.
- 문제 자체는 간단한데, 처음 원소들 중에서 가장 빈도수가 높은 원소를 구하는 부분에서 주의가 필요하다.
- 딕셔너리 기반의 자료구조를 이용해서 계산하면, Hash table hack에 의해 TLE가 난다. 그것을 피하기 위해서 여기에서는 수열을 정렬한 뒤 순서대로 읽으면서 각각 원소의 빈도수를 세었다.
- 특히 이 문제는 Hash table hack에서 실제 예로 사용한 문제이다. 이 부분 구현 방법에 대한 분석은 링크 참고.
코드
ps/problems/codeforces/1665b.txt · 마지막으로 수정됨: 2026/05/17 15:25 저자 teferi
토론