[Codeforces Round #842 (Div. 2)] D. Lucky Permutation

 

 

---

https://www.acmicpc.net/problem/25577

25577번: 열 정렬정렬 정

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> list = new ArrayList<>();
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		HashMap<Integer, Integer> hashmap = new HashMap<>();
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			hashmap.put(arr[i], i);
			list.add(arr[i]);
		}
		Collections.sort(list);
		int[] comp = new int[N];
		int ind = 1, ans = 0;
		for(int i = 0; i < N; i++) {
			if(comp[i] != 0) continue;
			
			int v = i;
			while(comp[v] == 0) {
				comp[v] = ind;
				v = hashmap.get(list.get(v));
				ans++;
			}
			ind++;
			ans--;
		}
		System.out.println(ans);
	}
}

 

※ .1 3 7 6 5 8 2 4 일 때

 

※. 연산횟수는 그래프의 깊이만큼 이루어진다.

(원소가 자기위치에 있다면 0, 두 개의 원소가 바뀌어있으면 0->1, 세 개의 원소가 바뀌어 있으면 2)

 

※. 백준의 정답이 s라면 코드포스의 정답은 반드시 s+1, s-1이다.

(2, 1 ,5 ,3 ,4 와 같이 2,1이 이미 반전되어 있는 경우 s-1)

(이 경우 a[i]와 a[i+1]의 그래프 종류가 같다면 위와 같음)

 

(3,4,1,2 와 같이  작업을 하면 전부 정렬되어 있어 하나를 반전시켜줘야하는 경우 s+1)

(위의 s-1의 경우가 아니라면 모두 이 경우다. 백준에서 문제푼 것처럼 s는 사이클로 정렬한 최소횟수이다. 정렬된 배열 중 임의의 a[i]를 a[i+1]과 바꾸어 주어야 함으로 s+1)

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			long ans = 0;
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken()) - 1;
			}
			
			int ind = 1;
			int[] comp = new int[n];
			for(int i = 0; i < n; i++) {
				if(comp[i] != 0) continue;
				
				int v = i;
				while(comp[v] == 0) {
					comp[v] = ind;
					v = arr[v];
					ans++;
				}
				
				ind++; ans--;
			}
			boolean answer = false;
			for(int i = 0; i < n - 1; i++) {
				if(comp[i] == comp[i+1]) {
					answer = true;
					sb.append(ans-1).append('\n');
					break;
				}
			}
			if(!answer)
				sb.append(ans+1).append('\n');
		}
		System.out.println(sb);
	}
}