일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 개발공부
- Database
- 오라클
- 트랜잭션
- 명령어
- AWS
- jdbc programming
- 데이터베이스프로그래밍
- 데이터베이스
- 자바
- TDD
- CS
- dbms
- 공부
- DB
- 리눅스공부
- EC2
- 시스템프로그래밍
- JDBC
- 개발자
- 클라우드네이티브
- 쿼리
- 개발방법론
- 쿼리최적화
- 서버
- 컴퓨터
- 리눅스
- 데브옵스
- 클라우드
- sql
Archives
- Today
- Total
개발 블로그
백준 10973: 이전 순열(JAVA) 본문
https://www.acmicpc.net/problem/10973
이전에 풀었던 다음 순열 문제를 조금만 변형하면 되는 문제다. 전체적인 알고리즘 논리는 같다. 부등호 방향만 반대로 해주면 된다.
import java.util.*;
public class Main {
public static void swap(int [] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static boolean nextPermutation(int[] a) {
int i = a.length-1;
//뒤에서부터 a[i-1] > a[i]인 첫번째 부분을 찾는다.
while (i > 0 && a[i-1] < a[i]) {
i--;
if(i==0) break;
}
//i가 0이면 위의 루프를 다 돌았다는 의미 = 이미 오름차순으로 정렬되어 있음
if (i <= 0) {
return false;
}
//a[i..last] 중 a[i-1]보다 작은 수를 뒤에서부터 탐색
int j = a.length-1;
while (a[j] >= a[i-1]) {
j--;
}
//a[i-1]과 a[j]의 자리를 바꿈
swap(a, i-1, j);
//a[i..last]까지 내림차순 정렬
j = a.length-1;
while (i < j) {
swap(a, i, j);
i--; j++;
}
return true;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
if (nextPermutation(a)) {
for (int i=0; i<n; i++) {
System.out.print(a[i] + " ");
}
}
else {
System.out.println("-1");
}
}
}
'프로그래밍 > 백준 문제풀이' 카테고리의 다른 글
백준 1182: 부분수열의 합 (1) | 2022.11.17 |
---|---|
백준 10974: 모든 순열 (0) | 2022.10.13 |
백준 10972: 다음 순열(JAVA) (0) | 2022.10.12 |
백준 9095번: 1, 2, 3 더하기 (0) | 2022.10.03 |
백준 1748: 수 이어 쓰기 1 (0) | 2022.10.03 |