[실버3] 15654. N과M(5) (Java)

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

15654번: N과 M (5)

Naver Mcdonald's

---

※  문제를 요약하면 아래와 같습니다.

▶ N개의 자연수와 수열의 길이 M이 주어졌을 때 N개의 자연수 중에서 M개를 고른 수열을 모두 출력

▶  Input : 첫째 줄에 N과 M 공백으로 구분하여 입력, 다음 줄에 N개의 수가 공백을 기준으로 입력

▶  Output : 한 줄에 수열을 하나씩 출력, 이 때 반드시 사전 순으로 증가하는 순서로 출력

---

◈ Input - 1

3 1
4 5 2

◈ Output - 1

2
4
5

◈ Input - 2

4 2
9 8 7 1

◈ Output - 2

1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

◈ Input - 3

4 4
1231 1232 1233 1234

◈ Output - 3

1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 재귀는 시스템 스택에 쌓이는 성질을 이용, 이 때 쌓여있는 순서를 인덱스로 설정 하여 수열의 각 값을 저장

▶ 비내림차순 정렬 필요

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static boolean[] barrVisited;
    static int[] narrNums;
    static int[] narrStack;
    static int N, M;
    static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bReader.readLine());

        // N과 M 입력 받고
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        narrNums = new int[N]; // 입력받은 수 들의 배열
        narrStack = new int[M]; // 시스템 스택 배열
        barrVisited = new boolean[N];
        // 무슨다리만들기야 이거나 풀ㄷ어

        // 수 입력 받고 정렬해
        st = new StringTokenizer(bReader.readLine());
        for (int i = 0; i < N; i++) {
            narrNums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(narrNums);

        NandM(0);

        bWriter.close();
    }

    private static void NandM(int nIndex) throws IOException {
        // 기저 조건
        // M-1번 만큼 재귀 스택이 쌓였을 때
        // 저장된 것들 출력하자
        if (nIndex == M) {
            for (int i = 0; i < M; i++)
                bWriter.write(narrStack[i] + " ");
            bWriter.write("\n");
            bWriter.flush();
            return;
        }

        // arrNums에 저장되어 있는 수들을 시스템 스택 배열에 쌓자
        // arrNums의 인덱스는 중복 가넝
        for (int i = 0; i < N; i++) {
            if (!barrVisited[i]) {
                barrVisited[i] = true;
                narrStack[nIndex] = narrNums[i];
                NandM(nIndex + 1);
                barrVisited[i] = false;
            }
        }

    }

}

---

 

Good Luck! (피드백 감사합니다!)