[elice 알고리즘 코드 챌린지] Day 1 - 목표량

import java.io.*;

class Main {
    static int N;
    static char[] cArr;
    static int len;  // 수의 자릿수
    static int min;  // 출력값
    static char[] sel;  // 순열을 저장할 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strNum = br.readLine();
        N = Integer.parseInt(strNum);
        cArr = strNum.toCharArray();
        len = cArr.length;

        min = Integer.MAX_VALUE;
        sel = new char[len];
        perm(0, 0);
        System.out.println(min);
    }

    static void perm(int sidx, int check) {
        // base case - 순열 완성
        if (sidx == len) {
            String s = new String(sel);
            int i = Integer.parseInt(s);
            if (i > N) {
                min = Math.min(min, i);
            }
            return;
        }

        // recursive case
        for (int i = 0; i < len; i++) {
            if ((check & (1 << i)) > 0)  continue;  // i번째 원소를 이미 선택했으면 패스

            sel[sidx] = cArr[i];
            perm(sidx + 1, check | (1 << i));  // 방문처리 하고 내려보내기
        }
    }
}

 

1. 풀이 요약

이 문제는 주어진 정수의 자릿수를 재배열하여 주어진 정수보다 크면서 가장 작은 정수를 찾는 것입니다. 주어진 정수의 자릿수를 순열로 생성한 후, 조건에 맞는 최소 값을 찾는 방식으로 해결할 수 있습니다. DFS(깊이 우선 탐색)과 비트마스킹을 사용하여 순열을 생성하고, 각 순열을 정수로 변환하여 조건을 확인합니다.

 

2. 핵심 아이디어

1. 순열 생성:
   • 주어진 정수의 각 자릿수를 char 배열로 저장하고, 이를 이용하여 모든 가능한 순열을 생성합니다.
   • 순열 생성에는 DFS(깊이 우선 탐색)와 비트마스킹을 활용합니다.
2. 비트마스킹:
   • 방문 체크를 비트마스킹을 사용하여 구현합니다. 이는 각 자릿수의 선택 여부를 비트로 표현하여 효율적으로 관리할 수 있게 해줍니다.
3. 순열 검증:
   • 생성된 순열을 정수로 변환하고, 주어진 정수보다 큰 경우 그 값 중 최소 값을 찾아 저장합니다.

 

3. 참고 - DFS를 이용한 순열 생성

순열 생성 문제는 주어진 집합에서 가능한 모든 순열을 생성하는 문제입니다. 순열을 생성하는 일반적인 방법은 DFS(깊이 우선 탐색)를 사용하는 것입니다.

1. 방문 체크 배열:
   • 각 원소가 이미 사용되었는지 여부를 체크하기 위한 배열을 사용합니다.
   • 비트마스킹을 이용하여 방문 여부를 관리할 수도 있습니다.
2. 재귀 호출:
   • 현재 선택된 원소를 순열에 추가하고, 다음 재귀 호출을 통해 나머지 원소들을 선택합니다.
   • 모든 원소가 선택되면 완성된 순열을 처리합니다.
3. 기저 조건:
   • 순열이 완성되었는지 여부를 확인하고, 완성된 경우 결과를 처리합니다.

예제 코드

import java.util.ArrayList;
import java.util.List;

public class PermutationExample {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        perm(nums, new ArrayList<>(), visited, result);
        System.out.println(result);
    }


    static void perm(int[] nums, List<Integer> current, boolean[] visited, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            
            visited[i] = true;
            
            current.add(nums[i]);
            perm(nums, current, visited, result);
            current.remove(current.size() - 1);
            
            visited[i] = false;
        }
    }
}