👀 문제
https://www.acmicpc.net/problem/10973
👊 도전
1. 설계
- 인덱스 i로 배열을 역순 순회하며 a[i-1]> a[i]를 찾는다.
- 인덱스 j를 역순 순회하며 i<=j 중 a[i-1]> a[j]인 j를 찾는다.
- a[i-1]와 a[j]를 swap한다.
- 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. 설명
- 규칙을 찾아낸다
- 인덱스 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을 리턴, 아니라면 바뀐 배열을 출력한다.