공부 165일차: 백준 10973번 이전 순열 자바 java

10973 이전 순열

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

10973번: 이전 순열

 

 

 

---

백준 10972번 문제 다음 순열

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/308

공부 164일차: 백준 10972번 다음 순열 자바 java

이 문제와 매우 유사하다

반대로 생각하면 된다

public static boolean previousPermutation() {
    int i = nums.length - 1;
    while(i > 0 && nums[i-1] <= nums[i]) {    // 끝에서부터 오름차순인지 체크
        i--;
    }
    if(i < 1) {    // 전체 오름차순(즉, 맨첫번째 순열)
        return false;
    }
    
    int j = nums.length - 1;
    while(nums[i-1] <= nums[j]) {    // 오름차순이라면
        j--;    // 왼쪽으로 가면서 비교
    }
    
    swap(i-1, j);    // 자리 바꾸기
    
    j = nums.length-1;
    
    while(i < j) {
        swap(i, j);
        i++;
        j--;
    }
    return true;
}

거의 유사하고, 3번째, 11번째 줄의 부등호 방향만 바뀐다

 

그 과정은 다음과 같다

"4 1 2 3 5 6"
 
1. 끝에서부터 오름차순인지 체크
i = 5
 
5 <= 6
i = 4
 
3 <= 5
i = 3
 
2 <= 3
i = 2
 
1 <= 2
i = 1
 
4 > 1 → false i=1
 
 
2. 왼쪽으로 가면서 비교
i-1 = 0, j = 5
 
4 <= 6
j = 4
 
4 <= 5
j = 3
 
4 > 3 → false j=3
 
3. 자리 바꾸기
i-1 = 0, j = 3
3 1 2 4 5 6
 
4. j가 더 크면 계속해서 자리 바꾸기
i = 1, j = 5
 
1 < 6
3 6 2 4 5 1
i = 2, j = 4
 
2 < 5
3 6 5 4 2 1
i = 3, j = 3
 
4 == 4 → false i = 3, j = 3
 
최종 → "3 6 5 4 2 1"

이런 식으로 직접 구해본다면 알고리즘 과정을 이해하는 데 더욱 좋을 것이다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
static int[] nums;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        nums = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        if(previousPermutation()) {    // 그 다음 순열이 존재한다면
            for(int val : nums) {
                bw.write(val+" ");
            }
        }else {
            bw.write("-1");
        }
        bw.flush();
        bw.close();
        
    }
    
    // 이전 순열 있는지 체크
    public static boolean previousPermutation() {
        int i = nums.length - 1;
        while(i > 0 && nums[i-1] <= nums[i]) {    // 끝에서부터 오름차순인지 체크
            i--;
        }
        if(i < 1) {    // 전체 오름차순(즉, 맨첫번째 순열)
            return false;
        }
        
        int j = nums.length - 1;
        while(nums[i-1] <= nums[j]) {
            j--;
        }
        
        swap(i-1, j);    // 자리 바꾸기
        
        j = nums.length-1;
        
        while(i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }
    
    
    // 자리 바꾸기
    public static void swap(int n, int m) {
        int temp = nums[n];
        nums[n] = nums[m];
        nums[m] = temp;
    }
 
}

 

매우 유사한 문제라서 접근하기 쉬웠다한 번쯤 직접 구해보는 걸 추천한다

 

 

 

---