https://www.acmicpc.net/problem/25181
문제 요약
- 수열 A가 있고 적절히 섞어서 수열 B를 만들때
- Ai != Bi가 되도록 만들 수 있는지
- N = 5000, 숫자 = 10만
접근법
- 숫자별로 그룹을 지어볼 수 있음 + 정렬을 할 수 있음
- 가장 큰 그룹의 크기를 K라고 할때, K 만큼 쉬프트하면 K 보다 작은 그룹들은 당연히 숫자가 겹치지 않을 것임
- 그룹의 크기가 K인 것은 겹칠 수도 있고 안 겹칠 수도 있음 -> 나머지 크기의 합이 K보다 작다면 겹칠 것임
- 쉬프트한 상태로 매칭이 되었다고 보고, 위치에 맞게 출력
newbieski