백준 10974. 모든 순열

🅰 백준 10974. 모든 순열

10974번: 모든 순열

✏️ 문제 풀이

• 모든 순열은 다음순열이랑 똑같은 문제이다.
• 다만 들어오는 데이터를 1부터 N까지 따로 저장을 해줘서 np를 수행해 주면 된다.

✏️ 소스코드

package bruteforce;

import java.io.*;

public class Main_실버3_10974_손은성 {

	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());
		int numbers[] = new int[N];
		for (int i = 1; i <= N; i++) {
			numbers[i - 1] = i;
		}

		do { 
			// 모든 순열 출력
			for (int i = 0; i < numbers.length; i++) {
				sb.append(numbers[i]+" ");
			}
			System.out.println(sb);
			sb.setLength(0); // StringBuilder 초기화 방법
		} while (np(numbers));
	}

	// nextpermutaion 수행함수
	private static boolean np(int numbers[]) {
		int N = numbers.length - 1;

		// 가장 높은 꼭지점 탐색
		int i = N;
		while (i > 0 && numbers[i - 1] >= numbers[i])
			--i;
		// 가장 높은 꼭지점이 없으면 종료
		if (i == 0)
			return false;

		// 가장 높은 꼭지점 이전의 값과 맨 뒤의 값중 처음으로 나온 높은 수 swap
		int j = N;
		while (numbers[i - 1] >= numbers[j])
			--j;
		swap(numbers, i - 1, j);

		// swap 이후 꼭대기부터 오름차순으로 정렬
		int k = N;
		while (i < k)
			swap(numbers, i++, k--);

		return true;
	}

	// 오름차순을 위한 swap함수
	private static void swap(int numbers[], int i, int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}

}

 

✅ 후기

•