728x90
반응형
1. 오늘의 학습 키워드
[LeetCode] 869. Reordered Power of 2
정렬
2. 오늘의 학습 문제
문제
https://leetcode.com/problems/reordered-power-of-2/description/
You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.
Return true if and only if we can do this so that the resulting number is a power of two.
Example 1:
Input: n = 1
Output: true
Example 2:
Input: n = 10
Output: false
Constraints:
- 1 <= n <= 109
코드
import java.util.*;
class Solution {
static Map <String, Integer> map ; //가능한 n의 reorder를 키로 저장하는 맵
static int n_length;
static String numberStr;
static int cnt=1;
static boolean visit[];
public boolean reorderedPowerOf2(int n) {
map=new HashMap<>();
numberStr = Integer.toString(n); //n을 문자열로 변환
n_length=numberStr.length(); //n을 변환한 문자열의 길이
visit= new boolean[n]; //문자 방문 여부, false초기화
String temp="";
return reorder( temp );
}
static public boolean reorder(String temp) {
for (int i = 0; i < n_length; i++) {
if (temp.length() == 0 && numberStr.charAt(i) == '0') { // 맨 앞에 0이 오지 않게
continue;
}
if (!visit[i]) { // 현재 인덱스 문자를 방문하지 않았으면 추가
visit[i] = true; // 현재 문자 방문 처리
String newTemp = temp + numberStr.charAt(i); // 새로운 문자열 생성
if (newTemp.length() == n_length) { // 모든 문자를 다 사용한 경우
if (!map.containsKey(newTemp)) { // 새로운 순열이면
map.put(newTemp, cnt++);
if (isPowerOfTwo(Integer.parseInt(newTemp))) { // 2의 제곱인지 검사
return true; // 2의 제곱이면 조기 종료
}
}
} else {
if (reorder(newTemp)) { // 재귀 호출
return true; // 2의 제곱을 찾으면 조기 종료
}
}
visit[i] = false; // 백트래킹
}
}
return false;
}
static public boolean isPowerOfTwo(int num) {
return (num > 0) && ((num & (num - 1)) == 0);
}
}
처음 풀은 것으로, n을 문자열로 변환하고, 시작이 0이 아니게하여 재귀적으로 모든 재정렬 조합을 구하며
map에 키로 추가하고, 2의 제곱이면 true를 얼리 리턴하는 코드다. 테스트케이스를 통과하였으나 메모리 초과로 실패했다.
import java.util.*;
class Solution {
static int n_length;
static String numberStr;
static boolean visit[];
public boolean reorderedPowerOf2(int n) {
numberStr = Integer.toString(n); // n을 문자열로 변환
n_length = numberStr.length(); // n을 변환한 문자열의 길이
visit = new boolean[n_length]; // 문자 방문 여부, false 초기화
return reorder("");
}
static public boolean reorder(String temp) {
for (int i = 0; i < n_length; i++) {
if (temp.length() == 0 && numberStr.charAt(i) == '0') { // 맨 앞에 0이 오지 않게
continue;
}
if (!visit[i]) { // 현재 인덱스 문자를 방문하지 않았으면 추가
visit[i] = true; // 현재 문자 방문 처리
String newTemp = temp + numberStr.charAt(i); // 새로운 문자열 생성
if (newTemp.length() == n_length) { // 모든 문자를 다 사용한 경우
if (isPowerOfTwo(Integer.parseInt(newTemp))) { // 2의 제곱인지 검사
return true; // 2의 제곱이면 조기 종료
}
} else {
if (reorder(newTemp)) { // 재귀 호출
return true; // 2의 제곱을 찾으면 조기 종료
}
}
visit[i] = false; // 백트래킹
}
}
return false;
}
static public boolean isPowerOfTwo(int num) {
return (num > 0) && ((num & (num - 1)) == 0);
}
}
그래서 map을 제거하여 수정하여 통과했으나, 시간이 매우 많이 걸리는 문제가 있었다.
그래서 풀이를 참고했다.
import java.util.*;
/*제약사항 1 <= n <= 10^9에서,
2^29 < 10^9 <2^30이다. 따라서 2의 29제곱까지만 탐색하면 된다.
2^0=1 -> 00001
2^1=2 -> 00010
2^2=4 -> 00100
에서, 2의 제곱을 이진수로 표현하면 위와같이 표현할 수 있다.
따라서 제약사항에 대해 찾을 수 있는 2의 제곱은 2^0~2^29 총 30개이며,
n을 재조합하였을 때 2의 제곱이 되려면
1->1 (1)
23-> 32 (3, 2)
821, 182, 218 -> 128 (1, 2, 8)
이렇게 n에 2의 제곱수가 가지고 있는 모든 요소를 가지고 있는지를 확인하면 된다.
따라서 n이 가지고 있는 0~9의 각 개수가 2의 제곱수의 0~9의 각 개수와 모두 일치하는지 확인하면 된다.
그러므로, n의 0~9 각 개수를 구하고, 그 개수를 2^0~2^29의 0~9 각 개수와 비교해준다.
*/
class Solution {
public boolean reorderedPowerOf2(int N) {
int[] A = count(N); //n이 가지고 있는 0~9 각 개수를 배열로 저장
for (int i = 0; i < 30; ++i) //2^0~2^29와 비교
if (Arrays.equals(A, count(1 << i))) //1은 이진수로 01로 표현하고, 왼쪽으로 i씩 밀어 2의 제곱 표현한다.
return true;
return false;
}
// Returns the count of digits of N
// Eg. N = 112223334, returns [0,2,3,3,1,0,0,0,0,0]
public int[] count(int N) {
int[] ans = new int[10];
while (N > 0) {
ans[N % 10]++;
N /= 10;
}
return ans;
}
}
3. 오늘의 회고
- 2의 제곱이 나오면, 비트연산을 떠올리자
- 모든 숫자 조합을 찾고자 생각했는데, 더 쉬운 방법이 있었다. 반성하자!!
- 제약사항을 파악해서 어떤 것들을 찾아야하는지 생각하면 문제풀이가 간단해진다.
728x90
반응형