문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다.
둘째 줄부터 T개 줄에는 각 테스트 케이스가 주어진다.
테스트 케이스는 한 줄로 이루어져 있으며, 수 A이다. A는 최대 80자리 자연수이다.
각 테스트 케이스에 대해서, 한 줄에 하나씩 A의 다음수를 출력한다.
만약, A의 다음수가 없을 때는 BIGGEST를 출력한다.내가 이 문제를 보고 생각해본 부분
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); : 대량의 입력을 효율적으로 처리하기 위해 BufferedReader를 사용한다.
StringBuilder sb = new StringBuilder(); : 여러 테스트 케이스의 결과를 한 번에 모아서 출력하기 위해 StringBuilder를 사용한다.
이는 반복적인 System.out.println() 호출보다 훨씬 효율적이다.
int T = Integer.parseInt(br.readLine()); : 첫 줄에서 테스트 케이스의 개수 T를 읽는다.
테스트 케이스 반복:
for(int t = 0; t < T; t++) { ... } : T번 반복하며 각 테스트 케이스를 처리한다.
숫자 A 처리:
char[] A = br.readLine().toCharArray(); : 입력으로 받은 숫자 A는 최대 80자리이므로 String으로 받은 뒤 char 배열로 변환하여 각 자릿수에 쉽게 접근할 수 있도록 한다.
n은 A의 길이이다.
Pivot(i) 찾기:
int i = n - 2; : 배열의 뒤에서 두 번째 인덱스부터 시작한다. (마지막 인덱스는 n-1이다).
while(i >= 0 && A[i] >= A[i + 1]) { i--; } : 이 while 루프는 오른쪽에서 왼쪽으로 이동하며 오름차순이 깨지는 첫 번째 위치(i)를 찾는다.
즉, A[i]가 A[i+1]보다 작은 경우를 찾는 것이다.
987과 같은 내림차순 숫자열에서는 이 조건을 만족하는 i를 찾을 수 없게 된다.
"BIGGEST" 판별:
if(i == -1) { sb.append("BIGGEST").append("\n"); } : 만약 i가 -1이 되었다면, 이는 숫자 A의 모든 자릿수가 내림차순으로 정렬되어 있다는 뜻이다 (예: 987, 321).
즉, 현재 A가 해당 자릿수들로 만들 수 있는 가장 큰 숫자이므로 "BIGGEST"를 출력하고 다음 테스트 케이스로 넘어간다.
교환할 숫자(j) 찾기:
int j = n - 1; : 배열의 마지막 인덱스부터 시작한다.
while(A[j] <= A[i]) { j--; } : 이 while 루프는 A[i](pivot)의 오른쪽 부분(A[i+1]부터 A[n-1]까지)에서 A[i]보다 크면서 가장 작은 숫자 A[j]를 찾는다.
이렇게 해야 전체적으로 A보다 크면서 가장 작은 '다음수'가 된다.
두 숫자(A[i], A[j]) 교환:
char temp = A[i]; A[i] = A[j]; A[j] = temp; : A[i]와 A[j]의 위치를 바꾼다.
Pivot 뒤쪽 부분(Suffix) 뒤집기:
int start = i + 1; int end = n - 1; : i의 바로 다음 위치부터 배열의 끝까지를 부분 배열로 설정한다.
while(start < end) { ... } : 이 while 루프는 A[start]와 A[end]를 교환하며 start는 증가시키고 end는 감소시켜 부분 배열을 뒤집는다.
이 부분이 중요한데, A[i]를 교환하고 나면 A[i+1]부터 끝까지의 부분은 여전히 내림차순(또는 일부 내림차순)으로 되어 있는다.
이 부분을 뒤집으면 오름차순으로 정렬되는 효과를 내어, 전체 숫자에서 A보다 크면서 가장 작은 다음 순열이 완성된다.
결과 출력:
sb.append(new String(A)).append("\n"); : 완성된 char 배열 A를 String으로 변환하여 StringBuilder에 추가한다.
각 테스트 케이스마다 개행 문자를 넣어준다.
System.out.print(sb.toString()); : 모든 테스트 케이스가 끝난 후 StringBuilder에 저장된 모든 결과를 한 번에 출력한다.
br.close(); : BufferedReader 리소스를 닫는다.코드로 구현
package baekjoon.baekjoon_31;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 백준 2697번 문제
public class Main1236 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder(); // 효율적인 출력을 위해 StringBuilder 사용
int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수 T
for (int t = 0; t < T; t++) {
char[] A = br.readLine().toCharArray(); // A를 문자 배열로 변환
int n = A.length;
int i = n - 2; // 뒤에서 두 번째 인덱스부터 시작
// 1. 뒤에서부터 오름차순이 깨지는 지점 (i) 찾기
// A[i] < A[i+1]을 만족하는 가장 큰 i를 찾는다.
while (i >= 0 && A[i] >= A[i + 1]) {
i--;
}
if (i == -1) { // A[i] < A[i+1]을 만족하는 i가 없는 경우 (모든 자릿수가 내림차순)
sb.append("BIGGEST").append("\n");
} else {
int j = n - 1; // 뒤에서부터 시작
// 2. A[i]보다 크면서 가장 작은 A[j] 찾기 (A[i+1]부터 끝까지)
while (A[j] <= A[i]) {
j--;
}
// 3. A[i]와 A[j] 교환
char temp = A[i];
A[i] = A[j];
A[j] = temp;
// 4. A[i+1]부터 끝까지의 부분 배열을 오름차순으로 정렬 (뒤집기)
// A[i+1]부터 n-1까지의 배열을 뒤집으면 오름차순 정렬과 동일한 효과
int start = i + 1;
int end = n - 1;
while (start < end) {
char temp2 = A[start];
A[start] = A[end];
A[end] = temp2;
start++;
end--;
}
sb.append(new String(A)).append("\n"); // char 배열을 String으로 변환 후 추가
}
}
System.out.print(sb.toString()); // 결과 한 번에 출력
br.close();
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer