
https://www.acmicpc.net/problem/2413
문제분석
Greedy를 활용해 문제를 풀어야 한다.
최적 해는 다음과 같다.
1. 짝을 맞춰야 한다. n은 n-1과 위치를 바꾸는 것 밖에 안되기 때문.
2. n이 n-1보다 높은 자릿수(순열의 앞쪽(왼쪽))에 있을 때, 무조건 바꿔야 한다. 가장 작은 순열을 구해야 하기 때문.
3. 순열의 앞쪽(왼쪽)부터 짝을 찾아서 바꿀 수 있는지 여부를 확인해나아가야 한다.
코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[]args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] position = new int[N+1]; // index는 해당 숫자를 의미, value는 해당 숫자의 '순열에서의 위치'를 의미
int[] permut = new int[N]; // 순열 저장
boolean[] changed = new boolean[N]; // 변경 여부 저장. 인덱스는 '순열에서의 위치'를 의미
Arrays.fill(changed, false);
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N ; i++){
int target = Integer.parseInt(st.nextToken());
position[target] = i;
permut[i]=target;
}
for(int i = 0; i < N ; i++){
int num = permut[i];// 순열 i 번째 숫자
if(num>1){
int n_1p = position[num-1];
if(i < n_1p && !changed[i] && !changed[n_1p]){// i > n_1p : [5,3,4,2,1] 에서 5와 4의 관계. 둘의 위치 변경해야 함
changed[i]=true;
changed[n_1p]=true;
permut[i] = num-1;
permut[n_1p] = num;
position[num-1] = i;
position[num] = n_1p;
}
}
}
for(int i = 0; i < N; i++)bw.write(String.valueOf(permut[i])+" ");
bw.flush();
bw.close();
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1360 되돌리기 (0) | 2026.02.12 |
|---|---|
| [JAVA] 백준 1043 거짓말 (0) | 2025.10.04 |
| [JAVA] 백준 1135 뉴스 전하기 (0) | 2025.09.09 |
| [JAVA] 백준 1967 트리의 지름 (0) | 2025.09.06 |
| [JAVA] 백준 1167 트리의 지름 (0) | 2025.09.02 |