[백준]15650번 N과M(2) (java)

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

15650번: N과 M (2)

백준 15650번 N과 M(2) 문제 링크입니다.

 

핵심

https://kimtaesoo99.tistory.com/17

[백준]15649번 N과 M(1) (java)

위의 문제를 변형한 것인데, N과 M(1) 문제의 경우에는 중복되지 않는 수열을 출력하는 것이고, (2)는 (1)의 문제를 변형한 

오름차순 순열이다. 단순히 (1)의 코드를 조금만 변형하면 쉽게 풀린다.

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	public static int[] arr;
	public static boolean[] check;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		arr = new int[M];
		check = new boolean[N];
		btm(N, M, 0);
		System.out.println(sb);
	}

	public static void btm(int N, int M, int depth) {
		if (depth == M) {
		for (int i=0; i <arr.length; i++) {
				for(int j=0; j<arr.length-1; j++) {
					if(arr[j]>arr[j+1])return;
				}
				sb.append(arr[i]).append(' ');
			}

			sb.append('\n');
			return;
		}

		for (int i = 0; i < N; i++) {
			if (!check[i]) {
				check[i] = true;
				arr[depth] = i + 1;
				btm(N, M, depth + 1);
				check[i] = false;
			}
		}
	}
}

 

해설

우선 N과 M을 입력받고, int형 배열에는 M을 boolean형 배열은 N만큼의 크기로 생성한다.

이후 btm을 호출시킨다.

배열에 i+1 값을 넣는데, 만약 check 되지 않았다면(전에 사용) 사용함으로 바꾼다.

이후 재귀 호출을 하는데, depth의 값을 1 더하고 호출한다.

반복 후, depth의 값이 M과 같아지면, sb에 추가하는 작업을 해야 하는데,

여기서 N과 M(1)과 다른 차이점이 발생한다.

현재의 배열 값이 다음 배열 값보다 크면, 리턴 시킨다. 즉 sb에 그 배열은 추가되지 않는다.

이러한 과정을 반복하게 된다면, 오름차순의 순열만 sb에 추가된다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.