기초수학-연습 문제 풀이 1-1

import java.util.ArrayList;

public class Practice1 {
    public static ArrayList<ArrayList<Integer>> solution(int numRows) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> list = new ArrayList<>();

            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                } else {
                    int x = result.get(i - 1).get(j - 1);
                    int y = result.get(i - 1).get(j);
                    list.add(x + y);
                }
            }
            result.add(list);
        }
        return result;
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(solution(1)); // [[1]]
        System.out.println(solution(2)); // [[1], [1, 1]]
        System.out.println(solution(3)); // [[1], [1, 1], [1, 2, 1]]
        System.out.println(solution(4)); // [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
        System.out.println(solution(5)); // [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
    }
}

 

 

 

import java.util.Arrays;

public class Practice2 {
    public static void solution(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int idx = -1;
        for (int i = arr.length - 1; i >= 1; i--) {
            if (arr[i] < arr[i - 1]) {
                idx = i - 1;
                break;
            }
        }

        if (idx == -1) { //좌측보다 더 큰 오른쪽 수를 찾지 못한 경우
            System.out.println(Arrays.toString(arr));
            return;
        }

        for (int i = arr.length - 1; i > idx; i--) {
            if (arr[i] < arr[idx] && arr[i] != arr[i - 1]) {
                int tmp = arr[i];
                arr[i] = arr[idx];
                arr[idx] = tmp;
                break;
            }
        }

        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 2, 1};
        solution(arr); //[3, 1, 2]

        arr = new int[]{1, 9, 4, 7, 6};
        solution(arr); //[1, 9, 4, 6, 7]

        arr = new int[]{1, 1, 2, 3};
        solution(arr); //[1, 1, 2, 3]
    }
}

 

 

 

import java.util.ArrayList;

public class Practice3 {
    // # 1 기본 permutation 방법
    public static boolean solution(String s1, String s2) {
        boolean[] visited = new boolean[s1.length()];
        char[] out = new char[s1.length()];
        ArrayList<String> list = new ArrayList<>();
        permutation(s1.toCharArray(), 0, s1.length(), s1.length(), visited, out, list);

        for (String s : list) {
            if (s2.contains(s)) {
                return true;
            }
        }
        return false;
    }

    public static void permutation(char[] arr, int depth, int n, int r, boolean[] visited, char[] out, ArrayList<String> list) {
        if (depth == r) {
            list.add(new String(out));
        }

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


    // # 2 문제 규칙 찾아 해결
    public static boolean solution2(String s1, String s2) {
        final int ALPHABET = 26;

        if (s1.length() > s2.length()) {
            return false;
        }

        int[] cnt = new int[ALPHABET];
        for (int i = 0; i < s1.length(); i++) {
            cnt[s1.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s2.length(); i++) {
            cnt[s2.charAt(i) - 'a']--;

            if (i - s1.length() >= 0) {
                cnt[s2.charAt(i - s1.length()) - 'a']++;
            }
            boolean isZero = true;
            for (int j = 0; j < ALPHABET; j++) {
                if (cnt[j] != 0) {
                    isZero = false;
                    break;
                }
            }
            if (isZero) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        // Test code
        String s1 = "ab";
        String s2 = "adbak";
        System.out.println(solution(s1, s2)); // true
        System.out.println(solution2(s1, s2)); // true
        System.out.println();

        s1 = "ac";
        s2 = "car";
        System.out.println(solution(s1, s2)); // true
        System.out.println(solution2(s1, s2)); // true
        System.out.println();

        s1 = "ak";
        s2 = "aabbkk";
        System.out.println(solution(s1, s2)); // false
        System.out.println(solution2(s1, s2)); // false
    }
}