[BOJ] 3671. 산업 스파이의 편지

https://www.acmicpc.net/problem/3671

접근 방법

먼저 문제를 보았을 때 배열에 대한 순열이 필요하다는 것을 알았다.

하지만 여기서 평범하게 순열을 쓰면 { 1, 1, 1 } 에서

1번째 1 + 2번째 1 → 11 / 2번째 1 + 3번째 1 → 11 두 개의 값은 다르다고 인식을 할 것이다.

그렇기 위해 나는 어떠한 장치를 걸기로 하였다. 맨 처음에는 단순히 Visit을 배열로 생성하고

boolean타입으로 한 번 들렸다면 true값을 반환하게 만들었었다.

하지만 문제의 메모리 제한은 128 MB 이다.

그래서 메모리 초과가 발생하게 된다. ( 10000000 boolean타입이 두개 이기 때문에 )

해결방법은 3번, 4번 을 읽기를 바란다.

1. Decimal_arr (에라토스테네스의 체를 사용해서 구한 배열) 을 만들어 놓고

    static void getDecimal(){
            decimal = new boolean[LIMIT_NUM];
            decimal[0] = true;
            decimal[1] = true;
            for(int i=2; i*i<LIMIT_NUM; i++){
                for(int k=i*i; k<LIMIT_NUM; k+=i){
                    decimal[k] = true;
                }
            }
        }

2. 순열을 쓰면서

3. 소수인 값을 참조한다. → list에 값을 저장해놓고 Decimal_arr배열에서 해당 값을 소수가 아니라고 만들어 놓는다.

    // 2+3 번 내용.
    static void sort_array(int[] sort_arr, int depth, int r){
            if(r == 0){
                int k=1;
                int newValue = 0;
                for(int i=0; i<depth; i++){
                    newValue += sort_arr[i] * k ;
                    k *= 10;
                }
                if (!decimal[newValue]) {
                    list.add(newValue);
                    decimal[newValue] = true;
                }
                return;
            }
            for(int i=depth; i<number.length; i++){
                swap(sort_arr, depth, i);
                sort_array(sort_arr, depth+1, r-1);
                swap(sort_arr, depth, i);
            }
        }

4. 모든 순열의 값을 보고 난 뒤 List에 있는 값을 하나씩 빼면서 다시 Decimal_arr 배열의 소수 판정을 원상 복귀 시켜놓는다.

    while(!list.isEmpty()){
                    int num = list.remove();
                    decimal[num] = false;
                    ans++;
                }

Need Know

1. 순열
2. 에라토스테네스의 체 ( 소수 구하는 방법 )

전체 코드 ( Java )

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int c;
    static boolean[] decimal;
    static int[] number;
    static final int LIMIT_NUM = 10000000;
    static LinkedList<Integer> list;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        getDecimal();
        c = Integer.parseInt(br.readLine());
        for(int i=0; i<c; i++){
            ans = 0;
            list = new LinkedList<>();
            String str = br.readLine();
            number = new int[str.length()];
            for(int k=0; k<str.length(); k++){
                number[k] = Integer.parseInt(String.valueOf(str.charAt(k)));
            }
            solve();
            while(!list.isEmpty()){
                int num = list.remove();
                decimal[num] = false;
                ans++;
            }

            bw.write(ans + "\n");
        }
    }
    static void sort_array(int[] sort_arr, int depth, int r){
        if(r == 0){
            int k=1;
            int newValue = 0;
            for(int i=0; i<depth; i++){
                newValue += sort_arr[i] * k ;
                k *= 10;
            }
            if (!decimal[newValue]) {
                list.add(newValue);
                decimal[newValue] = true;
            }
            return;
        }
        for(int i=depth; i<number.length; i++){
            swap(sort_arr, depth, i);
            sort_array(sort_arr, depth+1, r-1);
            swap(sort_arr, depth, i);
        }
    }
    static void swap(int[] arr, int depth, int i) {
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
    }

    static void getDecimal(){
        decimal = new boolean[LIMIT_NUM];
        decimal[0] = true;
        decimal[1] = true;
        for(int i=2; i*i<LIMIT_NUM; i++){
            for(int k=i*i; k<LIMIT_NUM; k+=i){
                decimal[k] = true;
            }
        }
    }

    static void solve() throws IOException {
        for(int k=1; k<=number.length; k++){
            sort_array(number,0,k);
        }
    }
}