[Day1] 목표량

💡문제

• 시간 제한: 1초

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.

예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.

오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

 

지시사항

입력

• 첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다.
  • 1≤N≤999999
• 정답이 반드시 있는 경우만 입력값으로 주어집니다.

출력

• 다음날 풀 문제의 개수를 출력합니다.

 

입력 예시

364

출력 예시

436

 

---

💡알고리즘 설계

• 다음 순열(next permutation) 알고리즘을 사용
• 입력받은 문자를 배열로 변환
• 오른쪽에서 왼쪽으로 이동하며 처음으로 감소하는 요소 찾기
• 그 요소의 오른쪽에서 그 요소보다 큰 수 중 가장 작은 수를 찾아 교환
• 교환한 위치의 오른쪽 부분을 오름차순으로 정렬

 

💡코드

package com.example.java_algorithm.Elice.day1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 목표량 {
    // 1. 입력받은 문자를 배열로 변환
    // 2. 오른쪽에서 왼쪽으로 이동하며 처음으로 감소하는 요소를 찾음
    // 3. 그 요소의 오른쪽에서 그 요소보다 큰 수 중 가장 작은 수를 찾아 교환
    // 4. 교환한 위치의 오른쪽 부분을 뒤집음 (오름차순으로)
    // 5. 결과 출력
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String nStr = br.readLine().trim();
        int[] numbers = new int[nStr.length()];

        for(int i=0; i<nStr.length(); i++) {
            numbers[i] = nStr.charAt(i) - '0';
        }

        // 2. 오른쪽에서 왼쪽으로 이동하며 처음으로 감소하는 요소를 찾음
        int index = -1;
        for(int i=nStr.length()-2; i>=0; i--) {
            if(numbers[i] < numbers[i+1]) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            System.out.println(nStr); // 이미 가장 큰 순열인 경우
            return;
        }

        // 3. 그 요소의 오른쪽에서 그 요소보다 큰 수 중 가장 작은 수를 찾아 교환
        int swapIndex = index + 1;
        for(int i=index+1; i<nStr.length(); i++) {
            if(numbers[i] > numbers[index] && numbers[i] < numbers[swapIndex]) {
                swapIndex = i;
            }
        }
        int tmp = numbers[index];
        numbers[index] = numbers[swapIndex];
        numbers[swapIndex] = tmp;

        // 4. 교환한 위치의 오른쪽 부분을 뒤집음 (오름차순으로)
        Arrays.sort(numbers, index+1, nStr.length());

        for(int i=0; i<numbers.length; i++){
            System.out.print(numbers[i]);
        }
    }
}

 

💡시간복잡도

• 입력 처리: O(n), 여기서 n은 입력된 숫자의 자릿수
• 감소하는 요소 찾기: O(n)
• 교환할 요소 찾기: O(n)
• 정렬: O(n log n)
• 전체 시간복잡도: O(n log n)

이론적으로는 O(n log n)이지만, 실제 이 문제의 제약 조건 하에서는 O(1)에 가깝게 동작한다고 볼 수 있다. 즉, 입력의 크기와 관계없이 거의 일정한 시간이 소요된다.