728x90
문제
숫자 n이 happy number인지 여부 판단
happy number란 각 자리 숫자들을 각각 제곱한 값을 계속 더해가다가 결국 1이 되는 숫자를 말함
Example 1:
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
Example 2:
Input: n = 2
Output: false
풀이1
public static boolean isHappy(int n) {
int cnt = 0;
while (n != 1) {
int cal = 0;
String s = "" + n;
char[] arr = s.toCharArray();
for (char c : arr) {
cal += (c - '0') * (c - '0');
}
n = cal;
cnt++;
if (cnt >= 10) {
return false;
}
}
return n == 1;
}
- while문 사용
- n을 String 값으로 변환 후 다시 char 배열로 바꾸어 각각을 제곱하여 더하는 계산을 함
- cnt 변수를 사용하여 while문의 실행 횟수를 카운팅함
- cnt 변수가 10 이상일 경우 false 반환 (순환이라고 판단, 하지만 10으로 설정한 기준이 없음...)
- n == 1 반환
- 시간복잡도 : O(log N)
💬 어떻게든 통과시켜보려고 막 만든 코드... 통과된 게 신기할 정도
풀이2
public boolean isHappy2(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1) {
String s = n + "";
char[] arr = s.toCharArray();
int cal = 0;
for (char c : arr) {
cal += (c - '0') * (c - '0');
}
if (set.contains(cal)) {
return false;
}
set.add(cal);
n = cal;
}
return true;
}
- HashSet 사용
- 계산 과정은 똑같지만 set에 똑같은 계산값이 이미 존재한다면 순환된 것으로 판단하여 false 반환
- 시간복잡도 : O(log N)
💬 조금 더 보완된 풀이지만 여전히 int → String → char[] 의 변환 순서에서 벗어나지 못함
풀이3
public static boolean isHappy3(int n) {
Set<Integer> set = new HashSet<>();
while (!set.contains(n)) {
set.add(n);
n = getNextNumber(n);
if (n == 1) {
return true;
}
}
return false;
}
private static int getNextNumber(int n) {
int output = 0;
while (n > 0) {
int digit = n % 10;
output += digit * digit;
n = n / 10;
}
return output;
}
- HashSet 사용
- 나머지 계산을 사용하여 값을 계산
- 이하 풀이2와 동일
- 시간복잡도 : O(log N)
💬 int → String → char[] 의 변환 순서를 대체할 메서드 작성
'JAVA > Coding Test Study' 카테고리의 다른 글
[Easy] LeetCode - no.228 Summary Ranges : Java (0) | 2024.10.19 |
---|---|
[Easy] LeetCode - no.219 Contains Duplicate II : Java (0) | 2024.10.17 |
[Easy] LeetCode - no.1 Two Sum : Java (0) | 2024.10.17 |
[Easy] LeetCode - no.242 Valid Anagram : Java (2) | 2024.10.17 |
[Easy] LeetCode - no.290 Word Pattern : Java (0) | 2024.10.16 |