[백준] 16936. 나3곱2 (Java)

 

문제

16936번: 나3곱2

 

 

알고리즘

브루트포스 알고리즘, 해시맵 

 

 

풀이

수열 B의 원소와 개수를 해시맵에 저장하고 각 원소를 시작으로 dfs를 진행한다.

 

각 숫자를 사용할 수 있다면 (해시맵에 저장된 value가 1 이상이라면) 

수열 A에 수를 저장한 후, 해시맵의 value를 1 감소시키고 다음 두 가지 수로 분기한다.

 

1. 현재 수가 3으로 나누어떨어진다면 3으로 나눈 수

2. 2를 곱한 수 

 

N번 분기했다면 저장한 수열 A를 출력한다.

각 분기가 반환되면 수열 A에 마지막에 삽입된 현재 수를 삭제하고, 해시맵의 value를 다시 1 증가시켜야한다.

 

* 수열 B에 포함된 원소의 최댓값이 10¹⁸ 으로 int 범위를 초과하므로 long 자료형을 사용해야한다.

 

코드

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

public class Main {
	static int N;
	static Map<Long, Integer> map;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new HashMap<>();
		N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			long num = Long.parseLong(st.nextToken());
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		for (long num : map.keySet()) {
			List<Long> result = new ArrayList<>();
			dfs(1, num, result);
		}
	}

	private static void dfs(int count, long num, List<Long> result) {
		if (map.getOrDefault(num, 0) <= 0) return;
		map.put(num, map.get(num) - 1);
		result.add(num);
		
		if (count == N) {
			StringBuilder sb = new StringBuilder();
			for (long r : result)
				sb.append(r).append(" ");
			System.out.println(sb);
			System.exit(0);
		}

		if(num % 3 == 0)
			dfs(count + 1, num / 3, result);
		dfs(count + 1, num * 2, result);
		
		map.put(num, map.get(num) + 1);
		result.remove(result.size() - 1);
	}
}