B - 0 or 1 Swap

はじめに

たなしょです。

今回も自力で解けました。嬉しい！

問題文

{1,2,...,N} を並び替えた数列 p= {p1, p2, ... pN} があります。 あなたは一度だけ、整数 i,j(1 ≤ i < j ≤ N ) を選んで piと p j を入れ替える操作を行うことができます。操作を行わないことも可能です。

p を昇順にすることができるなら YES を、できないならば NO を出力してください。

制約

1. 入力は全て整数である。
2. 2≤N≤50
3. pは {1,2, ..., N} を並び替えた数列である。

考え方

数列を入力したら、もう片方の配列に入力した数列をコピーしてコピーした数列をsort関数で昇順ソートする。 入力した配列とソートされた配列を比較して同じでない場合、比較対象の二つの数字を検索し入れ替える（tswap関数）

入れか完了後再度比較し昇順であればYESを出力、違ければNOを出力する。

いざ実装

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>

using namespace std;

void tswap(vector<int>& data, int a, int b, int N);

int main()
{
    int N;
    int cnt = 0;
    int flg = 0;
    cin >> N;

    vector<int> data(N);
    vector<int> data2(N);

    for (int i = 0; i < N; i++) {
        cin >> data.at(i);
    }

    for (int i = 0; i < N; i++) {
        data2.at(i) = data.at(i);
    }

    sort(data2.begin(), data2.end());

    for (int i = 0; i < N; i++) {
        if (data.at(i) != data2.at(i) && cnt == 0) {
            // 入れ替え
            tswap(data, data.at(i), data2.at(i), N);
            // 1回しか実施できない
            cnt++;
        }
    }


    for (int i = 0; i < N; i++) {
        if (data.at(i) != data2.at(i)) {
            cout << "NO" << endl;   
            flg = 1;         
            break;
        }
    }

    if (flg == 0) {
        cout << "YES" << endl;   
    }


    return 0;
    
}

void tswap(vector<int>& data, int a, int b, int N)
{
    int tmp, num1, num2;

    for (int i = 0; i < N; i++) {
        if (data[i] == a) {
            num1 = i;
            tmp = data[i];
        } else if (data[i] == b) {
            num2 = i;
        }
    }

    tmp = data.at(num1);
    data.at(num1) = data.at(num2);
    data.at(num2) = tmp;
}

最後に

もっと効率の良い方法がありそうですね。

最後まで読んでいただいてありがとうございました。 もしよろしければtwitterアカウント（@piklus100yen）もフォローしていただけると幸いです！