Codeforces Round #743 (Div. 2)-B. Swaps

개인적으로 div2의 b번 문제로는 너무 어려웠다는 느낌을 받았었는데, 아니나 다를까 난이도 1400문제 였다...

열심히 공부해야지

문제설명

길이가 $n$인 두 배열 $a$, $b$가 있다. 배열 $a$에는 $1$ 부터 $2n$까지 홀수 정수가 무작위로 중복되지 않게 있고, 배열 $b$에는 $1$ 부터 $2n$까지 짝수 정수가 무작위로 중복되지 않게 있다.

당신은 다음 연산을 사용할 수 있다.

• 두 배열중 하나를 선택한다.
• $1$ 부터 $n-1$까지 index중 하나를 선택한다.
• 선택한 배열의 $i$번째 값과 $i+1$번째 값을 바꾼다.

우리의 목표는 a가 b보다 사전순으로 작은 배열이 되게 만드는 최소 연산의 수를 구해야한다.

두 배열의 $x$와 $y$의 길이가 같을때, 배열 $x$의 첫번째 원소가 배열 $y$의 첫번째 원소보다 작으면 x는 y보다 사전순으로 작은 배열이라고 한다.

입력

이 문제는 여러개의 테스트케이스로 이루어져 있다. 첫번째 줄에는 테스트케이스의 수 $t$가 주어진다. $(1\le t\le {10}^4)$

각 테스트케이스의 첫번째 줄에는 배열의 길이를 나타내는 정수 $n$이 주어진다. $(1\le n\le {10}^5)$

각 테스트케이스의 두번째 줄은 배열 $a$에 들어갈 $n$개의 정수 $a_1,a_2,.....,a_n$가 주어진다. $(1\le a_i\le 2n)$ 모든 $a_i$는 홀수이며, 중복되는 원소가 없다.

각 테스트케이스의 세번째 줄은 배열 $b$에 들어갈 $n$개의 정수 $b_1,b_2,.....,b_n$가 주어진다. $(1\le b_i\le 2n)$ 모든 $b_i$는 짝수이며, 중복되는 원소가 없다.

input
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8

output
0
2
3

출력

각 테스트케이스마다 배열$a$가 사전적으로 배열$b$보다 작게 만드는데 필요한 연산의 최소 개수를 출력한다.

문제접근

사용한 알고리즘: 그리디 알고리즘, 정렬
걸린 시간 : 00:19

이 문제는 처음 virtual contenst에 참여했을때는 못 푼 문제였고, editorial을 보고나서도 이해를 못했다.
이번 Round #743은 대체적으로 editorial이 부실했는데, 이 부실한 editorial을 안보고 문제를 이해할 수 없을까라는 고민이 이 블로그를 만들게 된 계기가 됐다.

일단 먼저 한 배열이 다른 배열보다 사전적 순서로 작다 는 문장의 의미를 해석해야한다. 이 문장을 처음 봤을때는 멘붕이 왔지만 코드포스 A,B,C는 생각보다 단순하다. 따라서 그냥 단순하게 생각해봤다. 이 문장의 의미는 말하는 그대로 각 배열의 첫번째 요소만 비교해서 한 배열의 첫번째 index에 있는 원소가 다른 배열의 첫번째 index에 있는 요소보다 작으면 그 배열은 다른배열보다 사전적으로 작다는 의미가 된다. 즉 배열의 첫번째 요소만 비교하면 되는 것이다.

그래서 내가 생각한 첫번째 접근법은 배열 $a$의 index $i$번째 요소(여기서 index는 $0$부터 시작한다고 가정한다.)의 원소$a_i$가 배열의 처음으로 오기 위해서는 i번 만큼의 swap연산이 필요하기 때문에 이중 for문으로 가능한 모든 경우의 수를 모두 확인하는 브루트 포스 방식을 사용했다. 각 배열의 원소는 중복하지 않고, $1$에 대응되는 숫자는 $2$겠거니라고 생각하면서 binary_search함수를 이용해서 찾았지만 틀렸다.

하지만 이 접근법은 틀렸고, 이것이 이 문제를 어렵게 한 주범이기도 했다.
사전적으로 작다는 뜻은 배열 $a$의 첫번째 원소보다 배열$b$의 원소보다 작기만 하면 되는 것이지 꼭 차이가 1만 나라는 법은 없기 때문이다. 이 부분에서 정렬과 그리디알고리즘이라는 키워드를 생각하지 못했고, 문제를 틀리게 된것 같다. 그렇다면 이 문제는 어떻게 해결할까? 위에서 보여준 3번째 test case를 사용해서 문제를 푸는 과정을 따라가보자.

1. 각 원소의 위치를 저장하는 크기 $2n+1$짜리 배열을 선언한다. 크기 $n$짜리 배열을 2개 선언했고, 각 배열의 원소는 중복이 되지 않기 때문에 크기$2n+1$짜리 배열에 충분히 담을 수 있다. 3번째 testcase의 위치 배열 idx의 모습이다. $3,0,4,1,1,2,0,4,2,3$ (맨 왼쪽부터 원소 1의 index idx[1], 원소 2의 index idx[2]... 원소 10의 index idx[10]이다.)
2. 이 문제는 홀수 값만을 담은 배열인 $a$가 $b$보다 사전순으로 작게 만드는 연산의 개수를 구하는게 목적이기 때문에 $a$배열을 중심으로 index 0과 가까운 index를 갱신해 나갈 것이다.
3. 배열의 index는 당연히 $1$ 부터 $10$까지 오름차순으로 정렬되어 있기 때문에 왼쪽부터 홀수만 순서대로 보면서 바로 전 index의 값이 현재 index의 값보다 작으면 그 index보다 작은 값이 배열상에서 먼저 위치한다는 뜻이 되므로, idx의 배열의 값을 작은 값으로 변경한다.
4. 여기서 이해가 안될 수도 있는데, 위에서 만든 idx배열을 보면서 이해해보자. 홀수만 뽑아서 보면 $3,4,1,0,2$이다. 각각 $1,3,5,7,9$가 위치한 배열 $a$의 index이다. idx[1]과 idx[3]을 비교해보자 idx[1]의 값은 3이고, idx[3]의 값은 4이다. idx[1] < idx[3]이기 때문에 idx[3]을 3으로 바꾼다. 왜 4를 3으로 바꾸냐고 말할 수 있다.
   배열 $a=7,5,9,1,3,b=2,4,6,10,8$이 있을때 $1$은 $3$보다 앞에 있다. 그렇다면 $a$가 $b$보다 사전순으로 작게 하려 할때, 1을 0번 index로 옮기는게 연산 횟수가 적게들까? 3을 0번 index로 옮기는게 연산 횟수가 적게 들까? 당연히 $1$을 옮기는데 최선의 선택이다.
   왜냐하면 홀수의 숫자가 작을 수록 더 많은 짝수가 이동을 하지 않아도 사전 순으로 작게 만들 수 있게 되기 때문이다. $3$을 맨 앞에 옮기면 $2$와 $4$의 위치를 바꿔야하는 추가 연산이 필요하지만 $1$이 맨앞에 있으면 모든 짝수가 이동을 하지 않아도 된다. 즉 최소 연산이 된것이다.
   3의 과정을 반복하면 idx배열은 $3,0,3,1,1,2,0,4,0,3$이 된다.
5. 이 배열을 가지고 $i$번째와 $i+1$번째 수를 더한 값의 최소를 구하면 바로 답이 된다. $i$번째는 홀수, $i+1$번째는 짝수이고, $i$번째 있는 홀수는 $i$번째보다 뒤에 있는 짝수보다 항상 작기 때문에 이런식으로 답을 구할 수가 있다.

소스코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int odd[n] = {}, even[n], idx[(n << 1) + 1];
        for(int i = 0; i < n; i++){
            cin >> odd[i];
            idx[odd[i]] = i;
        }

        for(int i = 0; i < n; i++){
            cin >> even[i];
            idx[even[i]] = i;
        }

        for(int i = 1; i <= (n << 1); i+=2)
            if(i > 1) idx[i] = min(idx[i - 2], idx[i]);

        int ans = 987654321;
        for(int i = 2; i <= (n << 1); i+=2)
            ans = min(ans, idx[i] + idx[i - 1]);

        cout << ans << "\n";
    }
}