https://www.acmicpc.net/problem/9081
9081번: 단어 맞추기
입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알
www.acmicpc.net
풀이 방법
알파벳을 숫자 1, 2, 3, 4...로 바꾸어 생각해본다. 숫자가 크면 사전 순으로 뒤인 것이다.
1. 맨 뒤부터 시작하여 처음 숫자가 감소하는 위치 idx1 을 찾는다.
2. 다시 맨 뒤부터 시작하여 idx1 의 숫자보다 큰 숫자를 만나면 그 위치를 idx2 라고 한다.
3. idx1의 숫자와 idx2의 숫자의 자리를 바꾼다.
4. idx1 위치 이후의 숫자들을 오름차순 정렬한다.
그림으로 쉽게 살펴보자

처음 감소하는 위치 idx1 이후의 숫자들 '4 3 3 1' 은 내림차순 정렬이 되어있다. 이는 '3 2' 로 시작하여 만들 수 있는 단어의 가장 마지막 단어라는 것을 의미한다. 따라서 '3 2'로 만들 수 있는 단어는 끝났다. 사전 순 다음 단어를 구하기 위해선 2의 자리에 2 이후의 숫자들 중 2보다 큰 것 중 가장 작은 것이 와야한다. '4 3 3 1' 은 내림차순 정렬이 되어 있으므로 뒤에서부터 시작하여 2보다 처음으로 커지는 숫자의 위치가 idx2가 되며 해당 숫자가 2와 바꿀 대상이 된다. idx1의 숫자와 idx2의 숫자를 바꾼 후엔 idx1 위치 이후의 숫자들을 오름차순 정렬한다.

오름차순 정렬을 하면 '3 3' 으로 만들 수 있는 사전 순 가장 앞인 단어가 된다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
String word = br.readLine();
char[] charArr = word.toCharArray();
int len = charArr.length;
int idx1 = -1;
int idx2 = 0;
// 처음 알파벳이 작아지는 (사전순 앞임을 의미) 위치
for(int j=len-1; j>0; j--) {
if(charArr[j-1] < charArr[j]) {
idx1 = j-1;
break;
}
}
// 주어진 단어가 마지막 단어라면 그대로
if(idx1 == -1) {
System.out.println(word);
continue;
}
// idx1 원소보다 큰 원소 찾기
for(int j=len-1; j>idx1; j--) {
if(charArr[idx1] < charArr[j]){
idx2 = j;
break;
}
}
// 알파벳 위치 바꾸기
char temp = charArr[idx2];
charArr[idx2] = charArr[idx1];
charArr[idx1] = temp;
Arrays.sort(charArr, idx1+1, len); // 오름차순 정렬
System.out.println(new String(charArr));
}
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 1189 컴백홈 자바(java) (1) | 2024.01.14 |
|---|---|
| 백준 2644 촌수계산 자바(java) (0) | 2024.01.14 |
| 백준 9017 크로스 컨트리 자바(java) (0) | 2023.12.21 |
| 백준 14501 퇴사 자바(java) (1) | 2023.12.21 |
| 백준 19236 청소년 상어 자바(java) (1) | 2023.12.20 |