더 이상 물러설 곳이 없다

ApplicationContext applicationContext = new AnnotationConfigApplicationContext(AppConfig.class);

// getBean(메서드 명, 메서드가 반환하는 객체의 타입) or getBean(메서드가 반환하는 객체의 타입)
MemberService memberService = applicationContext.getBean("memberService", MemberService.class);

프로젝트가 실행되면 @Configuration이 등록된 클래스 (=AppConfig) 에서 @Bean 이 달린 모든 메서드를 찾아 실행시킨 후 반환된 객체를 스프링 컨테이너에 등록해둔다. (스프링 컨테이너 == ApplicationContext)

이때 저장되는 객체의 이름은 호출된 메서드의 이름으로 한다. 또는 @Bean(name = "~~") 로 직접 설정도 가능하다.

(key : value == 메서드명 : 생성된 객체,  빈의 이름이 겹치지 않도록 해야한다)

출처 : www.inflearn.com/course/%EC%8A%A4%ED%94%84%EB%A7%81-%ED%95%B5%EC%8B%AC-%EC%9B%90%EB%A6%AC-%EA%B8%B0%EB%B3%B8%ED%8E%B8/dashboard

www.acmicpc.net/problem/15666

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 중복하여 사용될 수 있다.

3. 같은 수열의 같은 자리에 대해서는 숫자의 중복이 허용되지 않는다. 즉, 중복 수열은 허용하지 않는다.

4. 비내림차순 수열만 허용한다.

codeung.tistory.com/62?category=449370

N과 M (11) 에서 비내림차순 조건만 추가된 문제 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static boolean isNotDesc(int deptNow) {
        for(int i = 0; i < deptNow; i++) {
            if(permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if (!used.contains(num[i]) && isNotDesc(deptNow)) {
                used.add(num[i]);
                dfs(dept, deptNow + 1);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!used.contains(num[i])) {
                permu[0] = num[i];
                used.add(num[i]);
                dfs(m, 1);
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에 isNotDesc() 를 추가하여 해결

www.acmicpc.net/problem/15665

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 중복하여 사용될 수 있다.

3. 같은 수열의 같은 자리에 대해서는 숫자의 중복이 허용되지 않는다. 즉, 중복 수열은 허용하지 않는다.

codeung.tistory.com/60?category=449370

N과 M (9) 에서 숫자 중복 사용 가능 조건으로 변경된 문제

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!used.contains(num[i])) {
                permu[deptNow] = num[i];
                used.add(num[i]);
                dfs(dept, deptNow + 1);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!used.contains(num[i])) {
                permu[0] = num[i];
                used.add(num[i]);
                dfs(m, 1);
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에서 boolean[] check 를 제거하여 해결

www.acmicpc.net/problem/15664

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 여러번 사용될 수 없음. 단, 똑같은 숫자를 여러번 입력받은 경우는 각각을 다른 숫자로 취급

3. 여러번 입력받은 똑같은 숫자를 다른 숫자로 취급하긴 하지만 수열의 같은 자리에 대해서는 같은 숫자로 취급

즉, 중복 수열은 허용하지 않는다.

4. 비내림차순인 수열만 혀용한다.

codeung.tistory.com/60?category=449370

N과 M (9) 에서 비내림차순 조건만 추가된 문제

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static boolean isNotDesc(int deptNow) {
        for (int i = 0; i < deptNow; i++) {
            if (permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if (!check[i] && !used.contains(num[i]) && isNotDesc(deptNow)) {
                check[i] = true;
                used.add(num[i]);

                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        check = new boolean[n];
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!check[i] && !used.contains(num[i])) {
                check[i] = true;
                used.add(num[i]);
                permu[0] = num[i];

                dfs(m, 1);

                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에서 isNotDesc() 를 추가하여 해결

www.acmicpc.net/problem/15663

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1. 입력받은 N개 중 M개의 숫자를 고른 수열

2. 숫자는 여러번 사용될 수 없음. 단, 똑같은 숫자를 여러번 입력받은 경우는 각각을 다른 숫자로 취급

3. 여러번 입력받은 똑같은 숫자를 다른 숫자로 취급하긴 하지만 수열의 같은 자리에 대해서는 같은 숫자로 취급

즉, 중복 수열은 허용하지 않는다.

ex ) 

입력

4 2

9 7 9 1

출력

1 7

1 9

7 1

7 9

9 1

9 7

9 9

9를 두 번 입력받기는 했으나 91, 97, 99는 한번씩만 등장

중복 수열을 허용하지 않음.

programmers.co.kr/learn/courses/30/lessons/42839

비슷한 문제.

이 문제는 중복 수열을 허용해서 검사하더라도 해결이 가능하긴 하지만 중복 수열에 대한 검사를 배제하면 시간이 매우 단축됨

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(check[i] == false && used.contains(num[i]) == false) {
                check[i] = true;
                used.add(num[i]);
                permu[deptNow] = num[i];

                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        check = new boolean[n];
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if(check[i] == false && used.contains(num[i]) == false) {
                check[i] = true;
                used.add(num[i]);
                permu[0] = num[i];

                dfs(m, 1);

                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

DFS 마다 Set을 통해 중복 수열에 대한 재귀를 배제했다.

해당 수열의 해당 자리에서 이미 사용된 숫자는 다시 오지 못하도록 하여 재귀를 막았다.

사실 이 문제에서는 굳이 Set을 사용하지 않고 int 변수 하나만으로도 처리가 가능하다.

만들어낸 수열들의 출력 순서를 오름차순으로 해야한다는 조건 때문에 입력받은 N개의 숫자에 대해 미리 정렬을 해놓고 DFS를 돌리기 때문이다.

즉, int last를 통해 해당 수열의 해당 자리에서 마지막으로 쓰인 숫자만 기억하고 있다면 중복 수열을 배제할 수 있다.

하지만 정렬을 하지 않는 조건일 경우 입력받은 숫자가 1, 0, 1 순서로 되어있다면?

해당 수열의 해당 자리에서 1은 맨 처음에 이미 사용 되었지만 0이 사용된 후 last는 0으로 갱신될 것이기 때문에 그 이후에 1이 다시 올 수 있게 되어 중복수열이 발생하게 된다.

따라서, 

정렬을 반드시 해야하는 경우 : int 변수 하나로 메모리를 아끼며 해결 가능

정렬을 하지 않는 경우 : Set으로 메모리를 좀 더 써서 해결 가능

어차피 이 문제는 주어진 입력의 제한조건이 그리 크지 않았기 때문에 어떤 정렬 여부에 관계없이 어떤 경우라도 해결 가능한 Set을 사용하여 문제를 풀었다.

www.acmicpc.net/problem/15657

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

1. 입력받은 N개의 숫자 중 M개 선택한 수열

2. 숫자는 중복 사용 가능

3. 비 내림차순인 수열만 허용

codeung.tistory.com/58?category=449370

N과 M (7) 에서 비 내림차순 조건만 추가된 문제

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static boolean isNotDesc(int deptNow) {
        for(int i = 0; i < deptNow; i++) {
            if(permu[i] > permu[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if(isNotDesc(deptNow))
                dfs(dept, deptNow + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        for (int i = 0; i < n; i++) {
            permu[0] = num[i];
            dfs(m, 1);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에 isNotDesc() 하나를 추가하여 해결

www.acmicpc.net/problem/15656

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

1. 입력받은 N개의 숫자 중 M개 선택한 수열

2. 숫자는 중복 사용 가능

codeung.tistory.com/56

N과 M (5) 문제에서 중복 사용 가능 조건만 추가된 문제.

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            dfs(dept, deptNow + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        for (int i = 0; i < n; i++) {
            permu[0] = num[i];
            dfs(m, 1);
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에서 boolean[] check 제거하여 해결

www.acmicpc.net/problem/15655

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

1. 주어진 N개 숫자 중 M개를 고른 수열

2. 오름차순인 수열

codeung.tistory.com/56

N과 M (5) 문제에서 오름차순 조건만 추가됨

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringTokenizer st = null;
    static StringBuilder sb = null;
    static boolean[] check = null;
    static int[] permu = null;
    static int[] num = null;
    static int n, m;

    public static boolean isAsc(int deptNow) {
        for(int i = 0; i < deptNow; i++) {
            if(permu[i] >= permu[i + 1]) {
                return false;
            }
        }
        return true;
    }


    public static void dfs(int dept, int deptNow) {
        if (dept == deptNow) {
            for (int i = 0; i < dept; i++) {
                sb.append(permu[i]).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            permu[deptNow] = num[i];
            if(check[i] == false && isAsc(deptNow)) {
                check[i] = true;
                dfs(dept, deptNow + 1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        permu = new int[m + 1];
        num = new int[n];
        check = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);

        for (int i = 0; i < n; i++) {
            if(check[i] == false) {
                permu[0] = num[i];
                check[i] = true;
                dfs(m, 1);
                check[i] = false;
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

기존 코드에 isAsc() 하나를 추가하여 해결