이전 순열

문제

언어

  • JavaScript

문제 풀이 step 1

  • 백준 10972번 - 다음 순열 풀이 를 뒤집으면 풀 수 있습니다.
  • 다음 순열에서 알아봤듯이 모든 순열은 앞에 어떤 수로 시작하는 마지막 순열이고, 그것의 다음 순열은 어떤 수로 시작하는 첫 순열입니다.
  • 이번에는 어떤 값으로 시작하는 첫 순열인지 찾습니다. 그리고 어떤 값의 마지막 값을 뒤에서 자신보다 한 단계 작은 값과 SWAP 을 해주고, 어떤 값 이후의 수들을 뒤집어주면 됩니다.

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = input[1].split(" ").map(Number);

	// ? 찾기
	let i = n - 1;
	for (i = n - 1; i > 0; i--) {
		if (arr[i - 1] < arr[i]) continue;

		break;
	}

	// 첫 순열인 경우
	if (!i) return -1;

	// ? 보다 한 단계 작은 수 찾기
	let j = n - 1;
	for (j = n - 1; j > i - 1; j--) {
		if (arr[j] > arr[i - 1]) continue;

		break;
	}

	// SWAP
	[arr[i - 1], arr[j]] = [arr[j], arr[i - 1]];

	// ? 이후 내림 차순을 오름 차순으로 뒤집기
	j = n - 1;
	while (i < j) {
		[arr[i], arr[j]] = [arr[j], arr[i]];
		i += 1;
		j -= 1;
	}

	return arr.join(" ");
};

console.log(solution(input));