💣"나3곱2" - 16936번

🎃문제설명

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

💾입출력 예

입력	출력
6 4 8 6 3 12 9	9 3 6 12 4 8
4 42 28 84 126	126 42 84 28

알고리즘 분류

• 수학
• 정렬
• 정수론

🌟문제 이해 및 풀이계획

✏️순열을 이용하여 모든 배열을 구한 뒤 가능한 답이 나왔을 때 해당 배열을 출력하고 종료하려 했다.
✏️근데 dfs 중간에 메소드 종료 후 어떻게 main으로 빠져나가야 할 지 모르겠어서 그냥 전부 돌고 ArrayList에 담은 뒤 0번째만 출력해보기로 했다.
✏️여기서 런타임에러(InputMismatch)가 났는데, 배열B의 원소가 최대 10^18이므로 int형이 아닌 long형을 써야 에러가 나지 않는다! 문제를 꼼꼼히 읽자..

✍🏻내 코드1,2 + 오답코드

package BOJ;

import java.util.*;

/*
 * 2021.12.08 daily algo/commit
 * 
 * DFS
 */

public class boj_16936_2 {

	static ArrayList<long[]> answer = new ArrayList<long[]>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long[] arr = new long[N];
		long[] list = new long[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
//			arr[i] = sc.nextInt();
			arr[i] = sc.nextLong();
		}
		permutation(arr, visited, list, N, 0);
//		System.out.println(Arrays.toString(answer.get(0)));
//		for(int i=0; i<N; i++) {
//			System.out.print(answer.get(0)[i]+" ");
//		}
		sc.close();
	}
	
	public static void permutation(long[] arr, boolean[] visited, long[] list, int N, int depth) {
		if(depth == N) {
			if(calculation(list)) {
				long[] result = list.clone(); // 깊은복사를 해줘야 값이 바뀌지 않는다.
				answer.add(result);
				System.out.println(Arrays.toString(answer.get(0)));
				System.exit(0);
			}
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visited[i]) {
				visited[i] = true;
				list[depth] = arr[i];
				permutation(arr, visited, list, N, depth+1);
				visited[i] = false;
			}
		}
	}
	
	public static boolean calculation(long[] list) {
		for(int i=0; i<list.length-1; i++) {
			// 나3곱2가 맞다면
			if(list[i] / 3 == list[i+1] || list[i] * 2 == list[i+1]) continue;
			else return false;
		}
		return true;
	}

}

/* 시간초과 (실패코드) - DFS 모든 값을 탐색

public class boj_16936 {
	
	static ArrayList<long[]> answer = new ArrayList<long[]>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long[] arr = new long[N];
		long[] list = new long[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
//			arr[i] = sc.nextInt();
			arr[i] = sc.nextLong();
		}
		permutation(arr, visited, list, N, 0);
		System.out.println(Arrays.toString(answer.get(0)));
		for(int i=0; i<N; i++) {
			System.out.print(answer.get(0)[i]+" ");
		}
		sc.close();
	}
	
	public static void permutation(long[] arr, boolean[] visited, long[] list, int N, int depth) {
		if(depth == N) {
			if(calculation(list)) {
				long[] result = list.clone(); // 깊은복사를 해줘야 값이 바뀌지 않는다.
				answer.add(result);
			}
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visited[i]) {
				visited[i] = true;
				list[depth] = arr[i];
				permutation(arr, visited, list, N, depth+1);
				visited[i] = false;
			}
		}
	}
	
	public static boolean calculation(long[] list) {
		for(int i=0; i<list.length-1; i++) {
			// 나3곱2가 맞다면
			if(list[i] / 3 == list[i+1] || list[i] * 2 == list[i+1]) continue;
			else return false;
		}
		return true;
	}

}
*/

⚔️역시나 모든 배열을 구한 뒤 가능한 답을 출력하는 건 시간초과가 났다. 그래서 메소드 중간에 System.exit(0)로 강제 종료를 시켜 시간을 줄여보려 했지만 역시나 시간초과.

⚔️어차피 최악의 경우 순열 계산을 100!번 해야하기 때문에 순열+dfs로 구할 수가 없나..? 정확하게 다시한번 풀어봐야 할 것 같다.

⚔️그래서 강의를 보기로 했다.

강의내용

✔️어차피 주어지는 배열은 가능한 답이 최소 1개 이상 있기 때문에 안되는 경우는 제외한다.

✔️따라서 주어진 수들의 3으로 나누어 떨어지는 횟수를 계산 한 뒤 가장 많은 횟수를 가진 순서로 내림차순 하면 자연스럽게 순서가 정해진다.

✔️3으로 나누어 떨어지는 횟수가 같을 땐, 곱하기 2을 해주어야 하는데 오름차순으로 정렬해야 순서가 맞으므로 오름차순 정렬을 해주면 된다.

---

✔️우선 나는 이차원 배열 long[][]을 설정하고 0번째를 3으로 나눈 나머지의 횟수를 저장했고, 1번째를 실제 B배열의 값을 저장해 주었다.

✔️0번째로 우선 내림차순을 하고 0번째 값이 같은 경우 1번째 값을 비교하여 오름차순 해주었다.

✍🏻내 코드3 + 강의

package BOJ;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/*
 * 2021.12.07 daily algo/commit
 * 
 * DFS를 이용하여 모든 값을 구하고 답이되는 배열 한개를 출력하고자 했지만 시간초과.
 * 
 * 나누기3, 곱하기2 일 때
 * 먼저 3으로 나누어 떨어지는 횟수를 구하고 제일 많이 나누어 떨어지는 값이 먼저이므로 내림차순 정렬한다.
 * 다음 곱하기 2는 수가 커질수밖에 없으므로 3으로 나누어 떨어지는 횟수가 같은 값들은 오름차순 정렬해주면 된다.
 * 
 * compare 정렬 Long형일 때는 return값을 long으로 변환해줘야 함
 */

public class boj_16936 {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long[][] arr = new long[N][2];
		
		for(int i=0; i<N; i++) {
			arr[i][1] = sc.nextLong();
			long n = arr[i][1];
			while(true) {
				if(n % 3 == 0) { // 3으로 나누어 떨어지는 횟수
					arr[i][0] += 1;
					n /= 3;
				}
				else break;
			}
		}
		
		Arrays.sort(arr, new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				if(o1[0] == o2[0]) {
					// 0번째 인덱스가 같으면 1번째 인덱스는 오름차순
//					return (o1[1] - o2[1]); 
					return Long.compare(o1[1], o2[1]);
				}
				else {
					// 0번째 인덱스 내림차순
//					return (o2[0] - o1[0]);
					return Long.compare(o2[0], o1[0]);
				}
			}
		});
		
		for(int i=0; i<N; i++) {
			System.out.print(arr[i][1]+" ");
		}
		
		sc.close();
	}
	
}

❌시간초과는 벗어났지만 코드가 틀린이유를 찾기 어려웠는데 아무래도 compare후 정렬할 때 자료형 때문에 오답처리 되는 것 같았다.

✔️그래서 return값을 Long.compare()로 바꿔줬더니 통과했다.

💡정렬 문제가 나올 때 간단하게 Array.sort()를 이용하여 정렬했었는데, 이번 문제처럼 이차원 배열의 0번째와 1번째를 다르게 정렬해야 할 때에는 이용하기 어려우므로 정렬 방법을 다시 정리해봐야겠다.