[백준/java] 15650. N과M(2) , 백트래킹

문제 보기

문제

• 입력 : 수열에 넣을 수 있는 최대 자연수 N, 수열의 길이 M
• 출력 : 조건을 만족하는 수열들
  - 조건 1. 1~N의 자연수 중 중복없이 M개를 고른 수열
  - 조건 2. 오름차순

문제 풀이

백트래킹을 이용해, 매 순간 수를 수열에 넣을지 말지 선택하는 방법으로 답을 구할 수 있다.

// 선택할 숫자 num, arr의 숫자를 넣어야 할 인덱스 idx, 배열 arr, num을 배열에 넣을 지 여부 hasElement
    private static void makeArr(int num,int idx,int[] arr,boolean hasElement) {

        // hasElement = true일 시, num을 배열에 삽입
        if(hasElement){
            arr[idx] = num;
            idx++;
        }
        
        // 배열을 다 채웠을 시 출력 및 종료
        if (idx == M) {
            for(int i = 0; i < M; i++){
                sb.append(arr[i] + " ");
            }
            sb.append("\n");
            return;
        }

        // num 이 범위의 수 넘어가기 방지를 위해 N이면 종료
        if(num == N){
            return;
        }

        /* 백트래킹 */
        // 선택하는 경우
        makeArr(num+1,idx,arr,true);
        // 선택하지 않는 경우
        makeArr(num+1,idx,arr,false);
    }

문제의 조건 중, 크기가 양수인 부분수열 중에서 구하라 했기 때문에 공집합이 아닌 경우에만 고려해야 한다. 따라서, 공집합 여부임을 알 수 있는 hasElement를 추가했다.

시간복잡도

O(2^n)

느낀점

이전에 백트래킹 문제인 부분수열의 합을 풀고, 정리하느라 풀이가 바로 생각났다. 문제를 풀고, 정리하는 습관의 중요성을 느꼈다.