Menu

Subscribe

[JAVA/백준] SW 역량 테스트 준비-기초 | 브루트 포스: 다음 순열

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. 인덱스 i로 배열을 역순 순회하며 a[i-1]< a[i]를 찾는다.
  2. 인덱스 j를 역순 순회하며 i<=j 중 a[i-1]< a[j]인 j를 찾는다.
  3. a[i-1]와 a[j]를 swap한다.
  4. a[i]부터 뒤집는다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.Scanner;

/**
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int[] array=new int[n];
		boolean flag=false;
		for(int i=0;i<n;i++)
			array[i]=scan.nextInt();
		
		for(int i=n-1;i>0;i--) {
			if(array[i-1]<array[i]) {
				for(int j=n-1;j>=i;j--) {
					if(array[i-1]<array[j]) {
						int temp=array[i-1];
						array[i-1]=array[j];
						array[j]=temp;
						break;
					}
				}
				int k=n-1;
				while(i<k) {
					int temp=array[i];
					array[i]=array[k];
					array[k]=temp;
					i++;
					k--;
				}
				flag=true;
				break;
			}
		}
		
		if(!flag)
			System.out.println("-1");
		else
			for(int i=0;i<n;i++) 
				System.out.print(array[i]+" ");
	}
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 규칙을 찾아낸다
    • 인덱스 i를 역순 순회하며 a[i-1]< a[i]인 i를 찾는다.
    • 인덱스 j역시 역순 순회하며 a[i-1]< a[j]인 j를 찾는다. i<=j까지만 체크한다.
    • a[i-1]와 a[j]를 swap한다.
    • a[i]부터 원소들을 뒤집는다.
    • 위 과정을 진행했다면 입력받은 배열은 역순이 아니므로 flag를 통해 표시한다.
    • 2중for문을 탈출한 후 flag를 체크하여 입력받은 배열이 변경되었는지 확인한다.
    • 변경되지 않았다면 입력 배열이 역순이므로 -1을 리턴, 아니라면 바뀐 배열을 출력한다.

👏 해결 완료!

참고