algorithm
[Algorithm] LeetCode 202.happy number using HashSet
tonirr
2020. 5. 18. 00:41
class Solution {
public boolean isHappy(int a) {
String n = Integer.toString(a);
boolean isHappyNum = false;
int sum = 0;
char[] array = n.toCharArray();
for(int i = 0; i < array.length; i++){
int ans = Integer.parseInt(Character.toString(array[i]));
sum += ans*ans;
}
int sum1 = 0;
int j = 0;
while(sum1 != 1){
String sumToStr = "";
if(j == 0){
sumToStr = Integer.toString(sum);
} else{
sumToStr = Integer.toString(sum1);
}
j++;
char[] array1 = sumToStr.toCharArray();
sum1 = 0;
for(int i = 0; i < array1.length; i++){
int ans = Integer.parseInt(Character.toString(array1[i]));
sum1 += ans*ans;
if(sum1 == 1){
isHappyNum = true;
}
}
}
return isHappyNum;
}
}
원래 코드.. 굉장히 억지로 풀었고 시간초과도 났다. 아직 자료구조가 많이 부족한 듯 싶다.
아래는 LinkedHashSet 으로 푼것
- hashSet에 있는 contains함수를 사용해서 때마다 더해지는 sum을 n에 넣고 hashSet에 n을 저장한다.
- hashSet.contains(n)의 Big-O는 O(1)이다.
- n을 10으로 나눠서 나머지를 구하면 1의 자리부터 숫자를 분리할 수 있다.
- 예를들어 379라면
- 첫번째에는 9
- 두번째에는 7
- 세번째에는 3
- 네번째 돌때에는 3을 10으로 나누면 0이 나오므로 n > 0 조건을 만족하지 않아 루프가 끝난다.
- 숫자를 분리해서 제곱해서 sum에 더하고
- n을 10으로 나눈 값을 n에 넣는다.
- 나눠서 0이 되면 n에 sum을 대입하고 리턴한다.
- 예를들어 379라면
- 만약 제곱해서 더한 값이 1이 나오고 다음 루프를 돈다면 1이 이미 hashSet에 들어있으므로 hashSet.contains(n)의 조건에 만족한다.
- 루프에서 나오고 n == 1(true)값을 리턴한다.
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> hashSet = new LinkedHashSet<>();
while(!hashSet.contains(n)) {
hashSet.add(n);
int sum = 0;
while(n > 0){
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;
}
return n == 1;
}
}
- 기억할 것들
- LinkedHashSet과 HashSet의 차이
- LinkedHashSet은 순서를 고려하고 HashSet은 순서를 고려하지 않는다.
- LinkedHashSet에서 contains메소드로 해당 요소를 찾을 때 Big-O는 O(1)이다.
- LinkedHashSet과 HashSet의 차이