백준 25181 - Swap the elements (C++)

문제

• 문제 링크

  
   BOJ 25181 - Swap the elements 
  

• 문제 요약

길이 $N$의 수열 $A_n$이 주어진다.
이 수열에 대해, 서로 다른 두 원소를 골라 위치를 바꾸는 연산을 원하는 만큼 수행 후 수열 $B_n$을 만드려고 할 때,
모든 $B_i$에 대해 $A_i ≠ B_i$인 수열 $B_n$을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 5,000$

$1 ≤ A_i ≤ 100,000$

알고리즘 분류

• 애드 혹(ad_hoc)
• 해 구성하기(constructive)

풀이

곰곰이 생각해보면, 수열 $B_n$을 만들 수 없는 조건은 쉽게 도출할 수 있다.

가장 많이 등장한 수를 $x$라 할 때, $count(x) > ⌊ {N \over 2} ⌋$ 라면 조건을 만족하는 $B_n$은 존재할 수 없다.
비둘기집 원리에 의해 $A_i = B_i$ 인 $x$가 반드시 존재하게 되기 때문이다.

위를 적절히 판단 했다면, 이제 $B_n$이 반드시 존재하는 상황에서 어떤식으로 구성할 지 생각해보자.

---

사실 이것도 나이브하게 보면 $O(N^2)$ 풀이를 쉽게 떠올려 볼 수 있다.
임의의 위치 $b_i, b_j$에 대해, $a_i ≠ b_j$ 와 $a_j ≠ b_i$ 를 동시에 만족 한다면 $swap$이 가능 하다는 것을 이용하면 된다.

다행히 $N ≤ 5,000$ 이므로 $O(N^2)$도 정해로 치도록 출제 하신 것 같다.
그렇게 최적화를 생각하지 않고 아래 코드로 $AC$를 받은 후 다른 사람들의 풀이를 구경 했는데, 비교적 간단하게 $O(NlogN)$ 풀이를 구성할 수 있음을 깨달았다.

우선순위 큐를 이용해 원소 개수순으로 짝지어주거나, 정렬 후 $x + ⌊{N+1 \over 2}⌋$ 번째 원소와 바꿔주는 등..
차라리 처음부터 $N ≤ 10^5$ 정도 됐다면 좀 더 고민해봤을 듯 싶다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
unordered_map <int, int> M;
int a[5001], b[5001];
 
int main()
{
    int n; cin >> n;
    for (int i(1); i <= n; i++)
        if (cin >> a[i]; ++M[a[i]] > n >> 1)
            cout << -1, exit(0);
 
    memcpy(b, a, sizeof a);
 
    for (int i(1); i <= n; i++)
        for (int j(1); a[i] == b[i] && j <= n; j++)
            if (b[j] ^ a[i] && b[i] ^ a[j])
                swap(b[i], b[j]);
 
    for (int i(1); i <= n; cout << b[i++] << ' ');
}

comment

끝