문제

---

2992번: 크면서 작은 수

• 입력 예: 123
• 출력 예: 132

→ 주어진 입력보다 큰 순열 중 가장 작은 것을 찾아내는 문제

해결방법

---

순열

주어진 입력이 123인 경우 1, 2, 3 으로 나누어 순열을 해야함

→ 🤔String으로 입력을 받아서 int 배열에 하나씩 잘라서 넣어 작업하자!

BufferedReader, BufferedWriter

입력을 받고 출력할 때 Scanner보다 빠르게 동작할 수 있는 객체

✨String만 입력 및 출력 할 수 있다!!

이전에는 계속 Scanner와 System.out을 사용했는데 그래서 이 문제때문에 시간 날렸다..

문제 해결 flow

1. 입력받기

• String 타입의 입력을 받은 다음

• 그 입력을 한글자씩 잘라 배열에 넣음

  → split 사용 : 💡split의 return은 String Array!!

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();
String[] str = input.split("");  // 한글자씩 잘라서 String 배열에 넣음

int[] arr = new int[str.length];
for(int i = 0; i<n; i++){        // String 배열을 int 배열로 복사
	arr[i] = Integer.valueOf(str[i]);
}

2. min값 설정

입력값보다 큰 값들 중 min값을 찾기 때문에 min값을 설정해준다.

3. 순열

• 순열을 만들면서

  • 방문했는지 체크

  • 입력값보다 큰지 비교

  • min값과 비교

    해서 순열 값을 만들면서 min값을 계속해서 갱신

• 순열 방법

  • swap

  • 재귀

    static void perm(int origin, int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    	if (depth == r) {
    	  int tmp = arrToInt(output);
    	  if(tmp>origin){
    	     if(tmp<min){
    	      min = tmp;
    	      isChanged = true;
           }
        }
           return;
        }
    
        for (int i=0; i<n; i++) {
    	    if (visited[i] != true) {
    	      visited[i] = true;
            output[depth] = arr[i];
            perm(origin, arr, output, visited, depth + 1, n, r);
            visited[i] = false;
          }
        }
    }

코드

---

😗전체 코드!

import java.io.*;
import java.util.*;

public class BigAndSmallNumber {
    static int min = Integer.MAX_VALUE;
    static boolean isChanged = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        // input
        String input = br.readLine();
        String[] str = input.split("");

        int n = input.length();
        boolean visited[] = new boolean[n];
        int arr[] = new int[n];
        int output[] = new int[n];
        for(int i = 0; i<n; i++){
            arr[i] = Integer.valueOf(str[i]);
        }
        int t = arrToInt(arr);

        perm(t, arr, output, visited, 0, n, n);
        if(isChanged != true){ // 입력보다 큰 순열이 없을 경우
            bw.write("0");
        }
        else{
            bw.write(Integer.toString(min));
        }

        bw.flush();
        bw.close();
        br.close();
    }
    
    static void perm(int origin, int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
        if (depth == r) {
                int tmp = arrToInt(output);
                if(tmp>origin){
                    if(tmp<min){
                        min = tmp;
                        isChanged = true;
                    }
                }
                return;
        }

        for (int i=0; i<n; i++) {
            if (visited[i] != true) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(origin, arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    static int arrToInt(int[] arr){
        int res = 0;
        int size = arr.length;
        for(int i = 0; i<size; i++){
            res += arr[i]*Math.pow(10,size-i-1);
        }
        return res;
    }
}

순열을 int 배열로 동작시키면서 arrToInt() 함수를 만들었는데,

생각해보니 그냥 String 배열로 순열을 만들어서 비교할때만 int로 하면 됐을 것 같다..!