[Baekjoon] 2697_다음수 구하기

Silver II

문제(출처: https://www.acmicpc.net/problem/2697)

---

< 다음수 구하기 >

 

문제 풀이 

 

문제 예시에서 주어진 279134399742를 가지고 설명해 보자.

뒤에서부터 값을 확인하면서 현재 위치 값보다 뒤에 있는 값 중에서 큰 값이 있는지 확인한다.

먼저, 2는 마지막 값이므로 넘어간다.

다음 값인 4를 확인했을 때 뒤에 2밖에 없으므로 넘어간다.

그다음은 7이지만 뒤에 7보다 큰 값이 없으므로 넘어간다.

이렇게 진행했을 경우 3일 때 뒤에 큰 값이 있는 것을 확인할 수 있다. 이때 3보다 큰 값이 9,9,7,4와 같이 4가 있지만 다음 수를 출력하기 위해 4로 교체한다. 그럼 2791344가 되고 남아있는 39972를 오름차순으로 정렬해 출력한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class _2697_ { // 다음수 구하기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			String a = bf.readLine();

			ArrayList<Integer> list = new ArrayList<>();
			int idx = -1;
			int num = -1;

			for (int j = a.length() - 1; j >= 0; j--) {
				list.add(a.charAt(j) - '0');

				Collections.sort(list, Collections.reverseOrder());
				if (list.get(0) != a.charAt(j) - '0') {
					idx = j;
					for (int k = list.size() - 1; k >= 0; k--) {
						if (a.charAt(j) - '0' < list.get(k)) {
							num = list.get(k);
							break;
						}
					}
					break;
				}
			}

			if (idx == -1) {
				bw.write("BIGGEST\n");
			} else {
				String result = a.substring(0, idx);
				result += num;
				boolean flag = false;
				Collections.sort(list);
				for (int j = 0; j < list.size(); j++) {
					if (!flag && list.get(j) == num) {
						flag = true;
						continue;
					}
					result += list.get(j);
				}
				bw.write(result + "\n");
			}
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 개수
a : 수 A
list : 현재 값보다 큰 수를 찾기 위한 리스트
idx : 큰 수로 교체할 인덱스
num : 큰 수로 교체할 값
result : 다음 수

 

테스트 케이스 개수를 입력받는다. 테스트 케이스 개수만큼 수 A를 입력받는다. A를 가지고 다음 과정을 수행한다.

 

1) A를 뒤에서부터 탐색하며 list에 추가한다.

2) list를 내림차순으로 정렬 후 0번째 값과 방금 추가한 값이 일치하는지 확인한다.

3) 일치하면 현재 값보다 큰 값이 없으므로 계속해서 반복한다. 일치하지 않다면 현재 값보다 큰 값이 있다는 뜻이므로 idx를 현재 위치로 저장한다. list에 있는 값을 탐색하며 현재 값보다 큰 값 중에서 가장 작은 값을 찾아 num에 저장한 후 종료한다.

 

만약 idx 값이 -1이면 다음수가 없다는 뜻이므로 "BIGGEEST"를 출력한다. idx 값이 있다면 result를 A의 0부터 idx전까지 값으로 초기화한다. 그다음 바꿀 값인 num을 추가한다. list를 오름차순으로 정렬 후 num 값을 제외한 값을 순서대로 저장한다. 최종 A의 다음수인 result를 출력한다. 

---

---