[JAVA] 백준 15664번

[JAVA] 백준 15664번 - N과 M (10)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static StringBuilder sb = new StringBuilder();
	static int[] answerArr; // 정답을 저장할 배열
	static HashMap<Integer, Integer> numberCountMap; // 사용할 숫자의 중복개수
	static ArrayList<Integer> numberList; // 사용할 숫자

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answerArr = new int[M];

		numberCountMap = new HashMap<Integer, Integer>();
		numberList = new ArrayList<Integer>();

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

		while (st.hasMoreTokens()) {
			int num = Integer.parseInt(st.nextToken());

			if (numberCountMap.get(num) == null) { // 사용할 숫자 리스트에 1번만 값을 넣어줌
				numberCountMap.put(num, 1);
				numberList.add(num);
			} else if (numberCountMap.get(num) < M) { // 사용할 숫자의 중복개수를 넣어줌
				numberCountMap.put(num, numberCountMap.get(num) + 1);
			}
		}

		Collections.sort(numberList);

		int depth = 0;

		solution(depth);

		System.out.print(sb.toString());

	}

	private static void solution(int depth) {
		if (depth == M) {
			for (int num : answerArr) {
				sb.append(num).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 0; i < numberList.size(); i++) {
			if (numberCountMap.get(numberList.get(i)) > 0) {

				if (depth == 0 || (depth > 0 && answerArr[depth - 1] <= numberList.get(i))) {
					numberCountMap.put(numberList.get(i), numberCountMap.get(numberList.get(i)) - 1);
					answerArr[depth] = numberList.get(i);
					solution(depth + 1);
					numberCountMap.put(numberList.get(i), numberCountMap.get(numberList.get(i)) + 1);
				}

			}
		}
	}
}

백준 백트래킹 문제

 

정답을 맞춘 풀이방법

1. depth == 0  인경우 또는 이전 수열보다 현재수열이 크거나 같은경우에만 solution함수를 실행함

 

※ HashMap이 아닌 HashSet과 별도의 boolean[] 배열을 쓰는 방법도 있었음