문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

당신은 정렬되지 않은 1부터 증가하는 유일한 정수를 가진 배열을 갖게 된다. 당신은 제한된 횟수해서 2개의 요소를 바꿀 수 있다. 제한된 횟수를 넘지 않게 바꿔서 가장 큰 값을 가진 배열을 만들어라.

Example

arr = [1, 2, 3, 4]
k = 1

아래 배열은 다른 요소끼리 1번 바꾼 형태이다.

[2, 1, 3, 4][3, 2, 1, 4]
[4, 2, 3, 1]

초기 값을 포함한 4개 중에 가장 큰 값은 [4, 2, 3, 1]이다. 만약 k가 2보다 크거나 같으면 [4, 3, 2, 1]이 가장 큰 값이 된다.

Function Description

largestPermutation 함수를 완성해라. 가장 큰 값을 형태로한 배열을 반환해야 한다.
largestPermutation 함수는 아래와 같은 매개변수를 가지고 있다.

Constraints

• 1 <= n <= 10^5
• 1 <= k <= 10^9

Solved

정수 n을 선언하고 arr의 크기를 할당한다. 그리고 정수형 배열 position을 n + 1의 크기로 생성한다.

int n = arr.size();
int[] position = new int[n + 1];

그리고 position에 현재 값들이 어떤 인덱스에 있는지 저장한다.

for (int i = 0; i < n; i++) {
	position[arr.get(i)] = i;
}

바꿀 인덱스를 나타낼 정수 a를 선언하고, 0을 할당한다.
while문을 k가 0보다 크고 a가 n보다 작을 때까지 반복한다. 이때 arr의 a 값이 n - a와 같지 않으면 값을 바꿔주고 k를 감소시킨다. while문 끝에 a를 증가시킨다.

while (k > 0 && a < n) {
	if (arr.get(a) != n - a) {
		int temp = arr.get(a);
		int swapIndex = position[n - a];

		arr.set(a, n - a);
		arr.set(swapIndex, temp);
		position[temp] = swapIndex;
		position[n - a] = a;
		k--;
	}

	a++;
}

마지막으로 arr을 반환한다.

return arr;

All Code

public static List<Integer> largestPermutation(int k, List<Integer> arr) {

	int n = arr.size();
	int[] position = new int[n + 1];

	for (int i = 0; i < n; i++) {
		position[arr.get(i)] = i;
	}

	int a = 0;

	while (k > 0 && a < n) {
		if (arr.get(a) != n - a) {
			int temp = arr.get(a);
			int swapIndex = position[n - a];

			arr.set(a, n - a);
			arr.set(swapIndex, temp);
			position[temp] = swapIndex;
			position[n - a] = a;
			k--;
		}

		a++;
	}

	return arr;
}