[JAVA] 백준 15663번

[JAVA] 백준 15663번 - N과 M (9)

 

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) {
				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. 기존의 N과 M 유형들이 섞인 유형

2. 이전의 N과 M 풀이시 boolean isUsed[] 배열을 선언해서 true, false로 값을 체크했었음

3. 그러나 M(수열의 길이) 보다 작고 중복의 개수만큼 숫자를 사용하기 때문에 HashMap으로 사용한 값을 체크함

4. StringBuilder를 이용해 정답출력